Josephus problem

Shrinking the circle one elimination at a time

time O(n)space O(n)

Simulating the circle directly is the most literal reading of the problem: keep an array of who is still standing, repeatedly count k people from the current position and remove the k-th, and whoever is left is the survivor. Removing an element shrinks the array in place, so the next count simply resumes at the same index — the person who used to be next in line is now sitting right there. This mirrors the recursive idea (the survivor of a smaller circle maps onto the bigger one by shifting forward by k) but makes every intermediate state visible instead of unwinding a call stack.

Details

Animated on: n=5 people in a circle, eliminate every k=2-th person. Answer: position 3.

Problem:Josephus problemHard

Shrinking the circle one elimination at a time

step 1 / 10

[0]

[1]

[2]

[3]

[4]

5 people stand in a circle, positions 1..5. Counting k=2 people at a time and removing the k-th, over and over, until one remains. The circle is the live state — no separate "removed" list needed, since a shrinking array already models who is still standing.

start=0· arr[0] = 1

Pseudocode

1FUNCTION josephus(n, k)
2  circle <- [1, 2, ..., n]
3  idx <- 0
4  WHILE LENGTH(circle) > 1
5    idx <- (idx + k - 1) MOD LENGTH(circle)
6    REMOVE circle[idx] FROM circle
7    idx <- idx MOD LENGTH(circle)
8  RETURN circle[0]

← / → step · space play · Home restart

Every step in words

Show all 10 steps

5 people stand in a circle, positions 1..5. Counting k=2 people at a time and removing the k-th, over and over, until one remains. The circle is the live state — no separate "removed" list needed, since a shrinking array already models who is still standing.
Round 1: starting the count at position 0 (person 1), counting off 1, 2 lands the k-th count on person 2 at index 1 = (0 + 2 - 1) MOD 5. That person is eliminated next.
Person 2 is gone. 4 left: [1, 3, 4, 5]. Counting resumes from the very next survivor — the array shrinking in place is exactly why nobody needs to be relabelled or skipped over.
Round 2: starting the count at position 1 (person 3), counting off 3, 4 lands the k-th count on person 4 at index 2 = (1 + 2 - 1) MOD 4. That person is eliminated next.
Person 4 is gone. 3 left: [1, 3, 5]. Counting resumes from the very next survivor — the array shrinking in place is exactly why nobody needs to be relabelled or skipped over.
Round 3: starting the count at position 2 (person 5), counting off 5, 1 lands the k-th count on person 1 at index 0 = (2 + 2 - 1) MOD 3. That person is eliminated next.
Person 1 is gone. 2 left: [3, 5]. Counting resumes from the very next survivor — the array shrinking in place is exactly why nobody needs to be relabelled or skipped over.
Round 4: starting the count at position 0 (person 3), counting off 3, 5 lands the k-th count on person 5 at index 1 = (0 + 2 - 1) MOD 2. That person is eliminated next.
Person 5 is gone. 1 left: [3]. Counting resumes from the very next survivor — the array shrinking in place is exactly why nobody needs to be relabelled or skipped over.
Only person 3 is left standing. That is the answer to the Josephus problem for n=5, k=2: position 3.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Josephus problem in the editor All Recursion problems Back to roadmap