Find the Winner of the Circular Game
Asked at Goldman Sachs
Problem
Find the Winner of the Circular Game seats n friends in a circle and repeatedly removes every k-th person until one remains. It is the Josephus problem: simulate with a queue for an O(n * k) answer, or use the recurrence for O(n) time and O(1) space.
Asked At
| Company | Difficulty | |
|---|---|---|
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
How to Think About It
Simulation: put everyone in a queue, rotate k - 1 people to the back, remove the next one, repeat. That is O(n * k) — fine for the constraints but not optimal.
Key insight (Josephus): after removing one person from a circle of i, the survivor of the remaining i - 1 people is the same person, just with indices shifted by k.
Recurrence with 0-indexed positions: f(1) = 0 and f(i) = (f(i - 1) + k) % i. The answer is f(n) + 1.
Compute it iteratively from i = 2 to n — no recursion needed.
Walkthrough for n = 5, k = 2: f = 0, (0+2)%2 = 0, (0+2)%3 = 2, (2+2)%4 = 0, (0+2)%5 = 2 -> friend 3.
Optimal Approach
Step 1: pos = 0 (the winner in a circle of 1, 0-indexed).
Step 2: For i from 2 to n: pos = (pos + k) % i.
Step 3: Return pos + 1.
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Removing from the middle of a Python list or Java ArrayList during simulation — each removal is O(n), so the simulation is O(n²).
Mixing 0-indexed and 1-indexed positions in the recurrence. Work 0-indexed and add 1 at the end.
Presenting the recurrence without explaining the index shift — interviewers usually ask why it works.
Starting the loop at i = 1, which applies an extra shift.
Solution Code
def findTheWinner(n, k):
pos = 0
for i in range(2, n + 1):
pos = (pos + k) % i
return pos + 1Frequently Asked Questions
What is the Find the Winner of the Circular Game problem?
Find the Winner of the Circular Game seats `n` friends in a circle and repeatedly removes every `k`-th person until one remains. It is the Josephus problem: simulate with a queue for an `O(n * k)` answer, or use the recurrence for `O(n)` time and `O(1)` space.
How do you solve Find the Winner of the Circular Game?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Find the Winner of the Circular Game?
Find the Winner of the Circular Game is asked at Goldman Sachs. It is a medium difficulty problem.
What are common mistakes on Find the Winner of the Circular Game?
- Removing from the middle of a Python list or Java ArrayList during simulation — each removal is `O(n)`, so the simulation is `O(n²)`.
- Mixing 0-indexed and 1-indexed positions in the recurrence. Work 0-indexed and add 1 at the end.
- Presenting the recurrence without explaining the index shift — interviewers usually ask why it works.
- Starting the loop at `i = 1`, which applies an extra shift.