This is an elimination game. Friends stand in a circle, numbered 1 to n. Starting from friend 1, we count k positions clockwise and eliminate the person at that position. Then we restart the count from the next person and continue until only one person remains. We return that last person.

This is the Josephus problem, a well-studied problem in combinatorics. After each elimination, the problem reduces to a smaller version of itself with a shifted starting position. That recursive structure leads to a mathematical solution that skips the simulation entirely.

Key Constraints:

Intuition

Do exactly what the problem says: arrange friends in a circle, count k positions, remove the person at that position, and repeat. We represent the circle as a list and use modular arithmetic to wrap around the end.

From a current position, counting k people forward (including the current one) lands on index (currentIndex + k - 1) % size. We remove that element. Because removal shifts every later element one slot to the left, the element that was directly after the removed one now sits at the same index we just removed from, which is where the next count should start. This mirrors the problem statement directly, so it is straightforward to verify.

Algorithm

Visualization and Code

This approach is correct but quadratic, since each removal from a list takes O(n). The next approach replaces the simulation with a formula that computes the winner's position directly.

Intuition

After the first person is eliminated from a circle of n people, we are left with a circle of n-1 people, and the game continues from a shifted starting position. If we know the winner's position in the game of n-1 people, we can map it back to the original circle of n people. The Josephus recurrence does this mapping.

Define J(n) as the 0-indexed position of the winner in a circle of n people. The base case is J(1) = 0: with one person, that person wins. For larger n, the recurrence is J(n) = (J(n-1) + k) % n.

Algorithm

Visualization and Code

The recursive approach runs in O(n) time but uses O(n) space for the recursion stack. Since each call depends only on the result of the call below it with no branching, the same chain can be computed iteratively from the bottom up, dropping the stack to O(1) space.

Intuition

The recurrence is a straight chain: each value depends only on the one for n-1, with no branching and no memoization table. We can compute it from the bottom up instead of recursing top down.

Start with J(1) = 0. Then compute J(2), J(3), up to J(n), each time applying (previous + k) % currentSize. A single variable holds the running result, which is what brings the space down to O(1). The mathematics is identical to the recursive approach; only the direction of evaluation changes.

Algorithm

Visualization and Code