The Josephus problem is a classic counting-out puzzle: n people stand in a circle and you eliminate every k-th one, going around and around, until a single survivor remains. The question is simply which seat survives? The naive answer is to act it out, but a one-line recurrence skips all the walking.
The setup. Number the seats 0..n-1. Starting the count at seat 0, walk k living people forward;
the k-th is eliminated. Resume counting from the next survivor and repeat. For n = 7, k = 3 the
survivors fall in the order 2, 5, 1, 6, 4, 0, leaving seat 3 as the winner.
Intuition
Simulating the circle works but is slow: each elimination means counting past up to k living people, and you do that n - 1 times. The clever observation is what happens right after the first person dies.
Once seat k-1 is eliminated, you have n - 1 people left, and the count restarts from seat k. That sub-circle is just a smaller Josephus problem. If you already knew the answer for n - 1 people, you could reuse it — you just have to account for the fact that the smaller circle began counting k seats further along. That shift, wrapped around the current size, is the whole recurrence: J(n) = (J(n-1) + k) % n, anchored by J(1) = 0 (with one person, that person trivially wins).
Walk through it
Step through the animation on the right. The first phase simulates the circle of 7. The count pointer marks each eliminated seat as it falls.
Watch the kill order. Counting 0 -> 1 -> 2 removes seat 2. Resuming from 3, we count 3 -> 4 -> 5 and remove 5. From 6 we count 6 -> 0 -> 1 (wrapping past the top) and remove 1. The dead seats are skipped on later passes, so the next counts are 3 -> 4 -> 6 (removing 6), then 0 -> 3 -> 4 (removing 4), then 0 -> 3 -> 0 (removing 0). Seat 3 is never counted as the third — it survives.
The second phase throws the circle away and runs the recurrence. res starts at 0, then climbs i = 2..7 as res = (res + 3) % i, passing through 1, 1, 0, 3, 0, 3. It lands on 3 — the exact seat the simulation left standing, but found in a single pass.
The code, line by line
def josephus(n, k):
res = 0 # J(1) = 0, the base case
for i in range(2, n + 1):
res = (res + k) % i # fold one more person in
return res # 0-indexed survivorresis seeded to0: with a single person (i = 1), seat0is the survivor, so that is the base case.- The loop builds up from a circle of 2 to the full circle of
n. At iterationiwe already holdJ(i-1)inresand computeJ(i)from it. - Line 4 is the recurrence itself: shift the previous answer forward by
kto account for where the smaller circle started counting, then take% ito wrap inside the current ring size. - After the loop,
resholdsJ(n), the 0-indexed survivor. If the puzzle numbers people from 1, returnres + 1.
Complexity
| Case | Time | Notes |
|---|---|---|
| Recurrence | O(n) (moderate) | one pass building J(2) up to J(n) |
| Naive simulation | O(n * k) (moderate) | walk up to k seats for each of n eliminations |
O(1) (fast)The iterative recurrence is the winner: a single loop of n - 1 steps with one variable, so O(n) time and O(1) space. The straightforward simulation with a list or linked list is O(n * k) (or O(n log n) with an order-statistics tree), and a recursive form of the recurrence is also O(n) but risks a deep call stack for large n.
When to use / pitfalls
The signal is a problem that describes a circle and removing every k-th element until one is left — or any elimination game with a fixed step that wraps around. Mention the O(n) recurrence J(n) = (J(n-1) + k) % n and that it returns a 0-indexed seat. If asked for the actual elimination order rather than just the survivor, fall back to the simulation (a deque or circular linked list).
Two common slips. First, off-by-one in the indexing: the recurrence returns a 0-based seat, so add 1 if
the problem counts people from 1. Second, do not reset the modulus — at iteration i you wrap by i
(the current circle size), not by the original n; using n throughout gives wrong intermediate answers.
Practice
Using J(n) = (J(n-1) + k) % n with k = 3 and J(4) = 0, what is J(5)?
1. What is the base case of the Josephus recurrence (0-indexed)?
2. In the recurrence J(n) = (J(n-1) + k) % n, what does the modulus n represent at iteration i?
3. For n = 7, k = 3, which 0-indexed seat survives?
4. Why is the iterative recurrence preferred over simulating the circle?