Find the Winner of the Circular Game

Find the Winner of the Circular Game

1. What is this problem about?

The Find the Winner of the Circular Game interview question is a classic problem known as the Josephus Problem. $N$ friends sit in a circle. Starting from friend 1, you count $k$ people clockwise and remove that person. You continue counting from the person after the one just removed until only one person remains. You need to find the ID of that sole survivor.

2. Why is this asked in interviews?

Companies like Goldman Sachs and Amazon use the Find the Winner of the Circular Game coding problem to test a candidate's ability to implement simulations or recognize recursive mathematical patterns. It evaluations your proficiency with Queue interview patterns (for simulation) and Recursion or Dynamic Programming (for the optimal $O(N)$ solution).

3. Algorithmic pattern used

There are two main ways to solve this:

1. Queue Simulation ($O(N \cdot K)$): Put all friends in a queue. Pop and push $k-1$ people to the back, and then pop (remove) the $k^{th}$ person. Repeat until the queue size is 1.
2. Iterative Formula ($O(N)$): Use the Josephus recurrence relation: $f(n, k) = (f(n-1, k) + k) \pmod n$. Starting from $n=1$, you can build up the answer for any $n$ in a single loop.

4. Example explanation

$n = 5, k = 2$

• Simulation:
  • Circle: [1, 2, 3, 4, 5]
  • Remove 2: [1, 3, 4, 5]
  • Remove 4: [1, 3, 5]
  • Remove 1: [3, 5]
  • Remove 5: [3]
• Survivor: 3.

5. Common mistakes candidates make

• Off-by-one: Josephus calculations usually work best with 0-based indexing ($0 \dots n-1$), but the problem is often 1-based. Forgetting to add 1 to the final formula result is common.
• Inefficient Deletions: Using an ArrayList and removing elements from the middle ($O(N^2 \cdot K)$) when a queue or the formula is much better.
• Recursion Depth: Failing to use the iterative version of the formula, which can hit stack limits for very large $n$.

6. Interview preparation tip

Master the Josephus Problem! It is a "top 50" interview question. While simulation is acceptable for beginners, knowing the $O(N)$ iterative formula demonstrates a higher level of mathematical and algorithmic maturity.