Quiz - Beauty of Numbers - Solution

One hint that should be helpful in building our solution is that we got to get retained after every wave of removal (until nobody else remains). That means it got to be really some special number or special kind of number. We could do what functional programmers would do. Write down the steps of removal for every queue size N, and it is not worth trying for very large N; in our case, even 20 or 30 could be large. But the point is we could iterate the steps manually and find a position K for every queue size N, where K is the position that remains after all the waves of removal. Once we are done with that, we should stare intensely 😂 on every K to derive a pattern, which would tell us something about those Ks, and with that we should be able to solve the problem.

Ok, let us try that real quick. I will be skipping the individual iterations and directly putting the number K for every N. You can do the homework of individually iterating the wave of removal.

NOTES

• A queue size of 1 does not make sense.
• Programmatic indices start from zero, while our home work\manual method indices start from 1.

I have done that manual iteration for you and produced the Ks. By now, you should have seen the pattern in the Ks. Yep, K should be a power of two. So to be lucky to escape the wave, we got to be at a position that is the highest possible power of two; for any given queue size N.

If we were to write a program (or a game with this logic), it would be composed of the following functions:-

int GetLuckyPosition(uint queueSize)
{
   // 0 and 1 are cases of invalid input.
   if (queueSize <= 1)
   {
      return 0;
   }

   // TODO: Suggest a better approach to find the K.
   for (int k = queueSize; k >= 2; --k)
   {
      if (IsPowerOfTwo(k))
      {
         return k;
      }
   }

   // Should never get here;
   return 0;
}

bool IsPowerofTwo(int num)
{
   return num & (num - 1) == 0;
}

In a power of two series, the on-bit keeps shifting to the left, and the same bit keeps shifting to the right during the wave of removals. I would say that K oscillates to settle at one position to survive. It is not about whether K is odd or even because when every wave strikes to remove, the even positions could become odds and vice versa. Only a power of two happens to remain at an even position, and hence it survives.