Solution: Rotating a Queue

We want a structure where an eliminated person is really removed, not just marked. A queue removes at the front, so removing is easy. The part that is not obvious is the counting. The count goes around the circle again and again, and a queue is a line with two ends, not a circle.

Take the counting on its own first, without any eliminations. Say we just want to visit every person, over and over, in circle order. Put everyone in a queue, then dequeue the person at the front and enqueue them again at the back. That person has had their turn, and the next person is now at the front. Do that again and the person after them comes to the front. Keep going, and after everyone has had a turn the first person is back at the front, and the whole thing repeats. Rotating the front to the back is how the queue visits people in circle order.

Now add the eliminations. Every person we rotate from the front to the back is a person we counted. So we keep a counter and increment it on each rotation. When the counter reaches k - 1, the person at the front is the k-th person counted, and that is the person who is eliminated. We dequeue them and do not enqueue them back. They are out of the queue, so no later rotation visits them. The person behind them is now at the front, which is where the rules say the count resumes, so we reset the counter and keep going. The queue gets one shorter with every elimination, and the last person left in it is the survivor.

Let’s trace the first elimination with n = 6 and k = 3. The queue starts with everyone in order, person 0 at the front:

┌───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │
└───┴───┴───┴───┴───┴───┘
  ▲                   ▲
front               back

Person 0 is counted: dequeue them, then enqueue them at the back.

┌───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ 0 │
└───┴───┴───┴───┴───┴───┘
  ▲                   ▲
front               back

Person 1 is counted the same way:

┌───┬───┬───┬───┬───┬───┐
│ 2 │ 3 │ 4 │ 5 │ 0 │ 1 │
└───┴───┴───┴───┴───┴───┘
  ▲                   ▲
front               back

Now person 2 is at the front, and the count has reached 3. Dequeue them and do not enqueue them back:

┌───┬───┬───┬───┬───┐
│ 3 │ 4 │ 5 │ 0 │ 1 │
└───┴───┴───┴───┴───┘
  ▲               ▲
front           back

Person 2 is gone, person 3 is at the front, and the next round of counting starts from them.

In code, the counter does not have to be a separate variable. Counting to k means rotating the first k - 1 people to the back and then eliminating whoever is at the front, so a for loop that runs k - 1 times is the counter, and the dequeue after the loop is the elimination. That also resets the count without any extra code, since the next round starts the loop over at 1.

Here is the implementation in Java:

public static int survivor(int n, int k) {
  Queue<Integer> circle = new ArrayQueue<>();
  // Enqueue all the people in the circle
  for (int i = 0; i < n; i++) {
    circle.enqueue(i);
  }

  int alive = n;
  while (alive > 1) {
    for (int counted = 1; counted < k; counted++) {
      int person = circle.front();
      circle.dequeue();
      circle.enqueue(person);  // counted, and survives this round
    }
    circle.dequeue();  // the k-th person counted is eliminated
    alive--;
  }
  return circle.front();  // the last person standing
}

The Queue ADT has no method that reports how many items it holds, so the loop cannot ask the queue whether one person remains. We track the number of living people in the alive variable instead.

You can check the method against n = 6 and k = 3. The eliminations happen in the same order as before, 2, 5, 3, 1, 4, and the survivor is 0. The rotations within each round work the same as the ones we traced above, so here we look at the queue only at the moment after each elimination. After 5 is eliminated:

┌───┬───┬───┬───┐
│ 0 │ 1 │ 3 │ 4 │
└───┴───┴───┴───┘
  ▲           ▲
front       back

After 3:

┌───┬───┬───┐
│ 4 │ 0 │ 1 │
└───┴───┴───┘
  ▲       ▲
front   back

After 1:

┌───┬───┐
│ 4 │ 0 │
└───┴───┘
  ▲   ▲
front back

After 4 is eliminated, alive drops to 1, the while loop stops, and front reports the survivor:

┌───┐
│ 0 │
└───┘
  ▲
front, back

With n = 1, the loop never runs and front returns person 0. With k = 1, the inner loop never runs, so people are dequeued in order and person n - 1 is the last one remaining.

What does this cost? Start with the cost of a single elimination. The inner loop runs k - 1 times, and each pass does a constant amount of work: one front, one dequeue, one enqueue, each $O(1)$ (amortized for enqueue). The final dequeue adds a constant amount more. So one elimination costs $O(k)$.

Now count the eliminations. The game starts with n people and ends with one, so there are exactly n - 1 eliminations. At $O(k)$ each, the total is $O(nk)$. (The setup loop that enqueues everyone adds $O(n)$, which does not change the answer.)

There is one difference between the queue and the real game. To move the count past a person, we move that person from the front of the line to the back. In the real game, the people stand still and the count moves around the circle.