The Josephus Problem

n people stand in a circle, numbered 0 to n - 1. Starting from person 0, count k people around the circle and eliminate the k-th; continue counting from the next person. Who is left at the end? The question shows up directly ("find the winner of the circular game") and as a test of whether you can turn a simulation into a recurrence.

Intuition

Simulation is straightforward: keep the circle in a queue, rotate it k - 1 places, and remove the front. That costs about O(n * k), or O(n^2) when k is large, and it is the only way to get the full elimination order.

The recurrence comes from renumbering. In a circle of n people, the first person eliminated is number (k - 1) mod n. The game then continues among n - 1 people, starting from the person right after the eliminated one. Renumber that person as 0 and keep going; the smaller game has the same shape, so its survivor is J(n - 1) in the new numbering. Converting back to the original numbering just shifts by k:

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

Evaluating it from n = 1 upward gives the survivor in O(n) time and O(1) space. For the 1-indexed version of the question, add 1 at the end.

Special case k = 2. Write n = 2^m + L with 0 ≤ L < 2^m. After L eliminations, 2^m people remain and the next count starts at person 2L; with a power-of-two number of people and k = 2, the person who starts the counting survives. So J(n) = 2L (0-indexed). In binary, the 1-indexed answer is n with its leading 1 moved to the end.

Huge n, small k. One full pass around the circle removes about n / k people at once (people k - 1, 2k - 1, ...). Solving the smaller game of size n - n // k recursively and mapping its answer back gives an O(k log n) algorithm, which handles n = 10^18.

When to use it in interviews / OAs

• "Players sit in a circle, every k-th one leaves, who wins?" (1-indexed: add 1 to the recurrence result.)
• "Last remaining number in a circle" questions and children's counting games.
• As a follow-up to a simulation: "your solution is O(n * k); can you do O(n)?"
• When the problem asks for the full elimination order, you need simulation (a queue, or an order-statistics tree for O(n log n)).

Template

Simulation with a queue

from collections import deque


def elimination_order(n: int, k: int) -> list[int]:
    """Order in which people 0..n-1 leave when every k-th person is removed."""
    circle = deque(range(n))
    order = []
    while circle:
        circle.rotate(-((k - 1) % len(circle)))  # bring the k-th person to the front
        order.append(circle.popleft())
    return order

The O(n) recurrence

def josephus(n: int, k: int) -> int:
    """0-based position of the survivor."""
    survivor = 0  # J(1) = 0
    for size in range(2, n + 1):
        survivor = (survivor + k) % size  # J(size) = (J(size - 1) + k) mod size
    return survivor

k = 2 in O(1)

def josephus_k2(n: int) -> int:
    """Survivor (0-based) when every second person is removed."""
    highest = 1 << (n.bit_length() - 1)  # largest power of two <= n
    return 2 * (n - highest)

O(k log n) for very large n

def josephus_large(n: int, k: int) -> int:
    """Same answer as josephus(n, k); fast when n is huge and k is small."""
    if n == 1:
        return 0
    if k == 1:
        return n - 1
    if k > n:  # fewer than k people: fall back to one step of the recurrence
        return (josephus_large(n - 1, k) + k) % n
    removed = n // k  # one pass removes people k-1, 2k-1, ..., removed*k - 1
    res = josephus_large(n - removed, k) - n % k  # survivor among the rest, renumbered
    if res < 0:
        res += n  # it lies in the tail after the last removed person
    else:
        res += res // (k - 1)  # skip over the removed positions
    return res

The recursion depth is about k ln n, so keep k small (when k exceeds n the function falls back to one person per call, which is only fine for small n).

Complexity

• Queue simulation: O(n * min(n, k)) time, O(n) space; it also yields the elimination order.
• Recurrence: O(n) time, O(1) space.
• k = 2 closed form: O(1).
• josephus_large: O(k log n) time and recursion depth.

Common pitfalls

• 0-based versus 1-based numbering. The recurrence is 0-based; convert at the end.
• Counting k versus skipping k. "Remove the k-th person" means rotate k - 1 places; "skip k people, then remove the next" means k + 1. Check with a tiny example.
• Using list.pop(index) for large n. Each pop is O(n), so the simulation is O(n^2); fine for n up to about 10^4.
• Running the recurrence downward. It has to be evaluated from size 1 up to size n (or recursively, which costs O(n) stack depth in Python).
• Applying the k = 2 formula to other k. There is no simple closed form for general k.

Interview variations

• Find the winner of the circular game (1-indexed, n up to a few hundred): simulation or josephus(n, k) + 1.
• Last number remaining in a circle of 0..n-1 removing every m-th: exactly josephus(n, m).
• Elimination order for large n: a Fenwick tree or segment tree over people still in the game, finding the next person to remove by order statistic in O(log n).
• Varying step sizes (step k_i in round i): use the same renumbering trick in reverse: J = (J + k_i) mod size processed from the last round back to the first.