Solution: Marking the Eliminated

Perhaps the simplest approach is to keep a record of who was eliminated, count around the circle, and skip over the eliminated people. Let’s turn that directly into code.

The record of who is eliminated can be a boolean array: eliminated[i] is true once person i is eliminated. Counting around the circle means moving from index to index and wrapping past the end back to 0, and we know how to do that: it is the same modulo arithmetic we used in the circular array. Let’s put that in a helper:

private static int nextAlive(int current, boolean[] eliminated) {
  int i = (current + 1) % eliminated.length;
  while (eliminated[i]) {
    i = (i + 1) % eliminated.length;  // skip over eliminated people
  }
  return i;
}

With that helper, the algorithm follows the rules of the game: count k people starting from the current person, eliminate the k-th, and resume the count at the next living person.

public static int survivor(int n, int k) {
  boolean[] eliminated = new boolean[n];
  int alive = n;
  int current = 0;  // the person the count starts at
  while (alive > 1) {
    int counted = 1;  // 'current' is the first person counted
    while (counted < k) {
      current = nextAlive(current, eliminated);
      counted++;
    }
    eliminated[current] = true;  // 'current' is the k-th person counted
    alive--;
    current = nextAlive(current, eliminated);  // the count resumes after the eliminated
  }
  return current;
}

You can check this against n = 6 and k = 3. The eliminations happen in the order 2, 5, 3, 1, 4, and the method returns 0. The special cases work out too. With n = 1, the loop never runs and person 0 is returned. With k = 1, the inner loop never runs, so the people are eliminated in order, and person n - 1 is returned.

So we have a correct solution. Is it a good one?

Look at what nextAlive does as the game goes on. Early in the game, almost everyone is alive, and moving the count forward by one living person takes one or two steps. But the array keeps every slot, so every elimination leaves a slot that all future counting has to step over. Late in the game, most of the slots are eliminated people. Take n = 1000 with two people left: moving from one living person to the other visits about 500 slots on average, almost all of them eliminated, and counting k people repeats that k times. So the work per elimination grows as fewer people remain.

The problem is that marking people as eliminated is not the same as removing them. What we want is a structure that gets smaller each time someone is eliminated, so that we never visit an eliminated person again.