The Josephus Problem Explained With Code and Interview Variants

Stackademic

Learn the Josephus circle elimination puzzle with simulation, an O(n) recurrence, and the k=2 trick interviewers still ask about.

The Josephus problem sounds like trivia until it shows up in a coding interview, a competitive programming contest, or a discrete-math homework set. The classic story—soldiers standing in a circle, eliminated every k-th person until one remains—packs a surprising amount of structure into a small puzzle.

If you are learning algorithms, Josephus is worth studying because it connects simulation, recurrence relations, and bit tricks. This article walks through the problem, a straightforward simulation, an efficient recurrence, and the variants interviewers like to ask.

The classic statement

n people stand in a circle, numbered 1 through n. Starting at person 1, you remove every k-th person going clockwise until one person remains. That survivor's original index is the answer.

Example: n = 7, k = 3.

Start: 1 2 3 4 5 6 7
Remove 3 → 1 2 4 5 6 7
Remove 6 → 1 2 4 5 7
Remove 2 → 1 4 5 7
Remove 1 → 4 5 7
Remove 7 → 4 5
Remove 5 → 4

The survivor is person 4.

When people search "josephus problem," they usually want either this walkthrough or working code.

Brute-force simulation with a list

The most readable approach models the circle as a list and repeatedly deletes the k-th element, wrapping indices with modulo arithmetic.

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

Time complexity is roughly O(n²) in the worst case because each pop shifts elements. For interview sizes (n ≤ 10⁴) that is usually fine; for large n, use the recurrence.

The recurrence for k = 2 (and building intuition)

When k = 2, the problem has a clean pattern linked to binary representations. For general k, the standard recurrence is:

Let J(n, k) be the survivor's 0-based index in a circle of size n.

J(1, k) = 0
J(n, k) = (J(n - 1, k) + k) % n

Convert to 1-based by adding one at the end.

def josephus_recurrence(n: int, k: int) -> int:
    survivor = 0
    for size in range(2, n + 1):
        survivor = (survivor + k) % size
    return survivor + 1

This loop is O(n) time and O(1) space—ideal when n is large.

Why the recurrence works

After the first elimination on a circle of size n, you are left with n − 1 people, but the circle has rotated: the next person after the removed one becomes the new starting point. That rotation is exactly the + k step, and shrinking the circle re-indexes everyone, which is the % size term.

Interview tip: explain the rotation story before reciting the formula. Interviewers reward understanding, not memorization.

Special case k = 2 and bit tricks

When every second person is eliminated, the survivor's 1-based index is:

2 * (n - 2^m) + 1

where 2^m is the largest power of two less than or equal to n.

def josephus_k2(n: int) -> int:
  m = 1
  while m * 2 <= n:
      m *= 2
  return 2 * (n - m) + 1

If you enjoy bit patterns, m is essentially highest power of two dividing the structure of n. This closed form is fast but less general than the recurrence.

Variants you should recognize

1-based vs 0-based answers. Always clarify with the interviewer. Many textbooks use 1-based survivor labels.

Different starting offsets. Some versions start eliminating from a person other than #1. That adds a constant shift to the index.

Finding the elimination order. Instead of the last survivor, output the full removal sequence. Simulation is often acceptable here; communicate complexity openly.

Very large n with mathematical shortcuts. For special k values, mathematical literature goes deeper than typical interviews require. In product interviews, stick to the recurrence unless they signal a math-heavy track.

Complexity comparison

ApproachTimeSpaceBest for
Linked-list simulationO(nk) typicalO(n)Clarity demos
Array simulationO(n²)O(n)Small n, quick tests
Recurrence loopO(n)O(1)General k, large n
Closed form (k = 2)O(log n)O(1)Specialty interviews

Circular linked-list approach

Another interview-friendly implementation uses a linked list so removal is O(1) once you locate the node. The cost is pointer bookkeeping and careful handling when the list shrinks to one node.

function josephusLinkedList(n, k) {
  class Node {
    constructor(value) {
      this.value = value;
      this.next = null;
    }
  }
  let head = new Node(1);
  let prev = head;
  for (let i = 2; i <= n; i++) {
    prev.next = new Node(i);
    prev = prev.next;
  }
  prev.next = head; // close the circle

  let current = head;
  let before = prev;
  while (before.next !== before) {
    for (let step = 1; step < k; step++) {
      before = current;
      current = current.next;
    }
    before.next = current.next;
    current = before.next;
  }
  return before.value;
}

Implementing this from scratch in an interview demonstrates pointer fluency—worth practicing even if you rely on the recurrence in production code.

Mathematical history (short)

The problem is named after Flavius Josephus, who—according to legend—chose a position in the circle to survive a Roman siege suicide pact. Historians debate the story, but the puzzle survived because it is a clean model of cyclic elimination.

Competitive programming platforms often tag problems "Josephus" when they expect the O(n) recurrence rather than literal simulation.

Debugging checklist

When your answer disagrees with a reference implementation:

  • Confirm 1-based vs 0-based indexing in the final print.
  • Verify whether the first person removed is the k-th in the current circle, not the k-th from the original labeling.
  • Check off-by-one errors when resetting the starting index after deletion.
  • For Python, remember list.pop cost if you are optimizing for scale.

Practice problems

  1. Implement both simulation and recurrence; compare outputs for random (n, k) pairs.
  2. Return the list of eliminated indices in order for n ≤ 500.
  3. Given k = 2 and large n, compute the survivor without a loop over n.
  4. Implement the linked-list version and measure runtime against the array simulation for n = 10_000.

FAQ

Is Josephus considered dynamic programming?
The iterative recurrence is often taught alongside DP, though it is a one-dimensional recurrence with O(1) transition—more "recurrence" than classic DP tables.

Does Josephus appear in real systems?
Rarely by name. The useful lesson is modeling circular buffers, round-robin scheduling, and index wrapping under deletion—common in games, networking, and resource pools.

What if k changes each round?
That is a different problem; state the assumption upfront before coding.

If you want extra practice, implement unit tests that compare all three approaches—array simulation, recurrence, and linked list—for every n from 1 to 200 with k values 2 through 7. Automated cross-checks build confidence before you rely on a single method in a timed interview.

The Josephus problem is small on the surface but sharp as a teaching tool. Learn the simulation to build intuition, learn the recurrence to finish efficiently, and keep the 1-based versus 0-based convention explicit so your final answer matches what the interviewer expects.