Find the Winner of the Circular Game: The Josephus Problem

Find the Winner of the Circular Game is LeetCode 1823, rated Medium. You have n friends sitting in a circle, numbered 1 through n in clockwise order. Starting from friend 1, you count k friends clockwise. The last person counted leaves the circle, and the next person clockwise becomes the new starting point. You repeat this until one friend remains. Return that friend's number.

For example, with n = 5 and k = 2, the elimination order is 2, 4, 1, 5, and the winner is 3. With n = 6 and k = 5, the winner is 1.

The approach

This is a classic problem known as the Josephus problem. There are two ways to solve it: direct simulation and a mathematical recurrence.

The simulation approach is the most natural. You maintain a list of the n friends. Starting from position 0, you count k steps forward (wrapping around with modular arithmetic), remove the person at that position, and repeat. Each removal requires finding the correct index in the shrinking list. Since you do n - 1 removals and each one involves counting through the list, the simulation runs in O(n^2) time.

The Josephus recurrence is far more elegant. The key observation is that after the first person is eliminated, you are left with a smaller version of the same problem, just with the starting position shifted. If you know the winner's position for a circle of size i - 1, you can compute the winner's position for a circle of size i. The recurrence is:

• For 1 person: winner = 0 (0-indexed)
• For i people: winner = (winner + k) % i

After computing the result for n people, add 1 to convert from 0-indexed to 1-indexed.

Simulation approach

def find_the_winner(n: int, k: int) -> int:
    friends = list(range(1, n + 1))
    idx = 0
    while len(friends) > 1:
        idx = (idx + k - 1) % len(friends)
        friends.pop(idx)
    return friends[0]

You start with a list [1, 2, 3, 4, 5] and index 0 (pointing at friend 1). Each round, you advance the index by k - 1 positions (because the current position already counts as the first step) and take the result modulo the current list size to wrap around. Then you remove the friend at that index. The index naturally points to the next person after the removal, so no adjustment is needed unless the removed person was at the end of the list, which the modulo handles automatically.

Josephus recurrence (optimal)

def find_the_winner(n: int, k: int) -> int:
    winner = 0
    for i in range(2, n + 1):
        winner = (winner + k) % i
    return winner + 1

Here is what happens step by step for n = 5, k = 2:

1. Start with winner = 0 (base case for 1 person)
2. i = 2: winner = (0 + 2) % 2 = 0
3. i = 3: winner = (0 + 2) % 3 = 2
4. i = 4: winner = (2 + 2) % 4 = 0
5. i = 5: winner = (0 + 2) % 5 = 2
6. Return 2 + 1 = 3

The loop builds up from the trivial 1-person case. At each step, (winner + k) % i accounts for the shift in positions when you add one more person to the circle. The final + 1 converts from the 0-indexed result to the 1-indexed answer the problem expects.

Visual walkthrough

Here is the full simulation for n = 5, k = 2, followed by the Josephus recurrence producing the same answer.

Notice how the recurrence reaches the same answer as the simulation but never needs to track who is still in the circle. It only tracks a single integer.

Complexity analysis

Simulation. You perform n - 1 removals. Each removal from a Python list takes O(n) in the worst case because elements after the removed index must shift. This gives O(n^2) total time and O(n) space for the list.

Josephus recurrence. You loop from 2 to n, doing one modular addition per iteration. That is O(n) time. You store only a single integer, so the space is O(1).

Building blocks

Josephus recurrence

The Josephus recurrence relates the winner's position in a circle of i people to the winner's position in a circle of i - 1 people: J(i) = (J(i - 1) + k) % i. This bottom-up construction appears in any problem where removing one element from a circular structure leaves a smaller version of the same problem. It is the foundation for all Josephus-type elimination questions.

Modular arithmetic in circular problems

Whenever indices wrap around a circle, modular arithmetic is the tool you need. The expression (idx + step) % size handles the wraparound in a single operation, avoiding manual bounds checking. This pattern shows up in circular buffer problems, rotating arrays, and any scenario where you move through a ring of elements.

Edge cases

• n = 1. Only one friend, so the answer is always 1. The Josephus loop does not execute, and winner + 1 = 0 + 1 = 1.
• k = 1. Every step eliminates the very next person. The last person standing is friend n.
• k = n. The counting wraps all the way around the circle before each elimination. The modular arithmetic handles this naturally.
• Large n (up to 500). The O(n) Josephus solution handles the upper constraint easily.

From understanding to recall

You have seen how the Josephus recurrence collapses a circle of eliminations into a simple loop with modular addition. The formula itself is short, but the intuition behind why (winner + k) % i works, the shift that accounts for the removed person, is the part that fades from memory first.

Spaced repetition makes it stick. CodeBricks isolates the building blocks of this problem, the Josephus recurrence and modular circular indexing, and drills them at increasing intervals. You reconstruct the solution from understanding rather than memorizing code. After a few review cycles, the recurrence becomes second nature.

Related posts

• Circular Array Loop - Circular indexing with modular arithmetic
• Nim Game - Game theory with mathematical patterns
• Elimination Game - Elimination sequences with index tracking