Skip to content
Tutorials Center
My learning

Topics

Lesson 71 of 225 Ā· Recursion and Backtracking

Josephus Problem

Solve the Josephus problem in Python: simulate the circle, derive the O(n) recurrence, and use the one-bit rotation trick for k = 2 in O(1) time.

Picture n people standing in a circle, numbered 1 to n. Starting at person 1, you count k people and remove the one you land on. Then you keep counting from the next person, removing every k-th, round and round, until only one person is left. Who survives?

This is the Josephus problem, named after a story about a group of soldiers who preferred a lottery of elimination to capture. It is a favorite interview question because it has three solutions of rising cleverness: a direct simulation, a tiny recursion that runs in O(n), and, for k = 2, a closed form that needs only a bit rotation. Along the way you will practice turning a process into a recurrence.

Simulating the circle

The most direct way is to keep the people in a list and track the position of the next count. If idx is where counting starts and the list has m people, the person removed is at (idx + k - 1) % m. After removal, counting restarts at that same index, because the next person has shifted into it.

For n = 7 and k = 3 the removal order is 3, 6, 2, 7, 5, 1, and person 4 survives:

flowchart LR
    A["circle: 1 2 3 4 5 6 7"] --> B["remove 3"]
    B --> C["remove 6"]
    C --> D["remove 2"]
    D --> E["remove 7"]
    E --> F["remove 5"]
    F --> G["remove 1"]
    G --> H["survivor: 4"]

Each arrow is one elimination with k = 3. Counting always restarts at the person after the removed one.

Python Simulate with a list

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cost: each pop from the middle of a Python list shifts elements, so the whole simulation is O(n²). A circular linked list removes in O(1) but needs O(k) steps to walk to the next victim, giving O(n·k). A deque with rotate(-(k-1)) has the same O(n·k) cost. For n in the thousands these are fine, but for n = 10^6 we need something better.

The recurrence

Let J(n) be the 0-based position of the survivor among n people with step k. Think about the very first removal. The person at 0-based position (k - 1) % n is gone, and counting restarts from the person after them. Now we have a circle of n - 1 people, and the problem looks identical, except the numbering is shifted: the person who is now "position 0" was originally at position k % n.

So if we know the survivor's position J(n-1) in the smaller circle, we can translate it back to the bigger circle by shifting it by k and wrapping around:

TEXT
J(1)   = 0
J(n)   = (J(n-1) + k) mod n

That is a loop that runs n - 1 times with constant work each time: O(n) time and O(1) space. At the end add 1 if you want 1-based numbering.

flowchart LR
    J1["J(1) = 0"] --> J2["J(2) = (0 + k) mod 2"]
    J2 --> J3["J(3) = (J(2) + k) mod 3"]
    J3 --> Dots["..."]
    Dots --> Jn["J(n) = (J(n-1) + k) mod n"]

Building the answer upward: the survivor of a circle of size m is the survivor of size m-1, shifted by k.

Python The O(n) recurrence, checked against the simulation

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same function written recursively is one line, J(n) = (J(n-1) + k) % n. It follows the recursive pattern you saw in recursion patterns: reduce the problem size by one, solve it, and adjust the answer on the way back. The loop above is just that recursion run bottom-up, which avoids stack depth problems for large n.

Special case k = 2: a bit trick

With k = 2 every second person is removed. Write out the survivors for small n (1-based):

n 1 2 3 4 5 6 7 8 9
survivor 1 1 3 1 3 5 7 1 3

The survivor resets to 1 each time n reaches a power of two, then grows by 2 with every additional person. Let p be the largest power of two with p <= n. Then:

TEXT
survivor(n) = 2 * (n - p) + 1

Why does this work? When the circle has exactly p people, one full lap removes everyone at even positions and leaves person 1 in front, so the survivor is 1. If there are n - p extra people, the first n - p removals bring the circle down to p people, and counting starts at person 2*(n-p) + 1, who is the survivor of that remaining power-of-two circle.

In binary this has an elegant reading. n - p removes the leading 1 bit of n. Multiplying by 2 shifts everything left, and + 1 puts a 1 into the empty low bit. So the answer is n rotated left by one bit, moving the leading 1 to the end. For n = 41 = 101001, the rotation gives 010011 = 19.

Python Closed form and bit rotation for k = 2

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions run in O(1) arithmetic on the word size (about O(log n) for the bit length), so even n = 10^18 is instant. If you want more of these tricks, see bit manipulation.

Faster for large n and small k

When k is small and n is huge, the O(n) loop can be sped up. If pos + k is smaller than size, the mod does nothing for several steps, so you can jump ahead many steps at once: compute how many steps t it takes before the sum would wrap, add t * k to pos, and advance size by t. This gives roughly O(k log n) time. It is a nice exercise in handling a loop with a "skip while nothing happens" idea. For interviews the O(n) recurrence is almost always enough.

Variations

  • Return the full elimination order quickly. A balanced tree or Fenwick tree with "find the j-th remaining person" lets you remove the i-th victim in O(log n), for O(n log n) total, even for varying k.
  • Start counting from a different person. Shift the final answer by the starting offset.

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. What does J(n) = (J(n-1) + k) mod n compute, with J(1) = 0?

    J(1) = 0 because a lone person survives. Each step maps the survivor's position in the circle of n-1 people back into the circle of n people.
  2. 2. What is the time complexity of the list-based simulation that uses pop(idx)?

    There are n-1 removals and each pop from the middle of a Python list shifts up to n elements.
  3. 3. For k = 2, who survives when n = 8?

    n = 8 is a power of two, so 2*(8 - 8) + 1 = 1. Every lap removes the even positions and person 1 is always left in front.
  4. 4. How can the k = 2 answer be described in binary?

    Removing the leading 1, shifting left and appending a 1 equals 2*(n - p) + 1, the same as rotating n's bits left by one place.

Summary

  • Josephus: remove every k-th person from a circle of n until one remains.
  • Simulating with a list is easy but O(n²); a deque or circular linked list gives O(nĀ·k).
  • The recurrence J(n) = (J(n-1) + k) mod n, J(1) = 0, gives the survivor in O(n) time and O(1) space.
  • For k = 2 the survivor is 2*(n - p) + 1, where p is the largest power of two not above n; this is n rotated left by one bit.
  • Always decide between 0-based and 1-based numbering before you trust the formula.

Next: Linear Search