Josephus Problem

Problem. $n$ people stand in a circle. Starting from position 1, every $k$-th person is eliminated, and the circle closes up. Who survives?

The recurrence — $O(n)$

Let $J(n,k)$ be the survivor’s 0-indexed position.

$J(1,k)=0,J(n,k)=(J(n-1,k)+k)\mathrm{mod}n.$

After the first elimination, $n-1$ people remain in a circle whose numbering is shifted by $k$.

int josephus(int n, int k) {                  // 0-indexed survivor
    int r = 0;
    for (int i = 2; i <= n; i++) r = (r + k) % i;
    return r;                                  // add 1 for 1-indexed
}

$O(n)$ time, $O(1)$ space.

The case $k=2$ — a closed form

$J(n,2)=2(n-2^{\lfloor {\log }_{2}n\rfloor }),$

or in one line: write $n$ in binary and rotate its leading 1 to the end.

$n=1b_{m-1}\dots b_0⟹J=b_{m-1}\dots b_{0}1.$

int josephus2(int n) {                         // 1-indexed survivor
    int highBit = 1 << (31 - __builtin_clz(n));
    return 2 * (n - highBit) + 1;
}

For $n=41$ (Josephus’s own legendary case with $k=3$, but with $k=2$): $41=101001_2\to 010011_2=19$.

The bit-rotation form is a good example of a combinatorial recurrence with a clean binary description — the same flavour as Hanoi’s ctz rule.

Large $n$, small $k$ — $O(k\log n)$

When $n$ is up to $10^{18}$ but $k$ is small, the recurrence can be batched: while $r+k<i$, many consecutive steps just add $k$ without wrapping, so they can be skipped in one jump.

long long josephusBig(long long n, long long k) {
    if (k == 1) return n - 1;
    long long r = 0;
    for (long long i = 2; i <= n; ) {
        if (r + k < i) {                       // how many steps until the next wrap
            long long steps = (i - r - 1) / k;
            steps = min(steps, n - i + 1);
            r += steps * k;
            i += steps;
        } else {
            r = (r + k) % i;
            i++;
        }
    }
    return r;
}

$O(k\log n)$ — the number of wraps is $O(k\log n)$ because each wrap roughly multiplies $i$ by $\frac{k}{k-1}$.

Variants

Variant	Method
Survivor’s position	the recurrence above
Order of elimination	simulate with an order-statistics tree or a BIT, $O(n\log n)$
$m$ survivors	run the recurrence from $J(m,k)$ upward
Elimination direction alternates	modify the recurrence
Variable step $k_i$	the same recurrence with $k_i$
Josephus on a line (no wraparound)	a different, simpler problem
$k=2$, huge $n$	the bit rotation, $O(1)$

Order of elimination in $O(n\log n)$

Keep the survivors in a BIT over positions; to find the $j$-th remaining person, do a BIT descent:

int kth(int k) {                               // k-th remaining, 1-indexed
    int pos = 0;
    for (int pw = 1 << LOG; pw; pw >>= 1)
        if (pos + pw <= n && bit[pos + pw] < k) { pos += pw; k -= bit[pos]; }
    return pos + 1;
}
// then repeatedly: cur = ((cur + k - 1 - 1) % remaining) + 1; erase kth(cur);

$O(n\log n)$ total, and it outputs the full elimination sequence — which most contest versions of this problem actually want.

The history

Flavius Josephus, in the Jewish-Roman war, was trapped with 40 companions who preferred suicide to capture. They arranged themselves in a circle to be killed every third man. Josephus — a mathematician — placed himself and a friend at the surviving positions.

Why it is worth knowing

It is the standard example of a problem where the recurrence is easy and the closed form is surprising. The $k=2$ bit rotation, and the batching trick for large $n$, are both techniques that transfer: whenever a recurrence adds a constant modulo a growing bound, batching the non-wrapping steps turns $O(n)$ into $O(k\log n)$.

See also: Tower of Hanoi · Fenwick Tree · Classical Problems