Find the Winner of the Circular Game - Video Solutions

Problem Overview: You have n friends standing in a circle. Starting from the first friend, every k-th friend is eliminated until only one person remains. The task is to return the label of the final survivor. This is a classic variation of the Josephus problem often solved with simulation or a direct mathematical recurrence.

Approach 1: Simulating the Process with a List (O(n*k) time, O(n) space)

This approach directly models the game. Store players 1..n in a list or queue and repeatedly remove the k-th player while moving around the circle. Maintain an index that advances by k - 1 positions each round using modulo arithmetic to wrap around the list. After removing a player, the next count continues from the same index because the circle shrinks. The process continues until only one element remains in the list. This solution is intuitive and mirrors the real game mechanics, making it useful for understanding the elimination process. However, list deletions and repeated traversal lead to O(n*k) time in the worst case.

The implementation often uses a dynamic array or queue structure from the array family. Each iteration performs an index calculation and removal, which shifts remaining elements. For large inputs, this repeated removal becomes the main bottleneck.

Approach 2: Mathematical Solution using Josephus Problem (O(n) time, O(1) space)

The circular elimination follows a well-known recurrence called the Josephus formula. Instead of simulating removals, compute the survivor position incrementally. If f(n, k) represents the winner among n players, the recurrence is:

f(n, k) = (f(n - 1, k) + k) % n

Start with the base case f(1, k) = 0 (0-indexed). Iterate from 2 to n, updating the survivor index each step. The final answer is converted to 1-indexed by adding 1. This approach eliminates the need for explicit simulation and avoids repeated deletions. The logic can also be written using recursion, though the iterative form avoids stack overhead.

This mathematical insight reduces the problem to a simple loop and constant memory usage. The algorithm runs in O(n) time and O(1) space, which is optimal for this problem.

Recommended for interviews: Start with the simulation idea because it shows you understand the circular elimination process. Then derive or mention the Josephus recurrence to reach the O(n) solution. Interviewers typically expect the mathematical approach since it demonstrates deeper algorithmic reasoning beyond straightforward simulation.