Josephus Problem

1. The Problem

n people stand in a circle numbered 0 to n-1. Starting from position 0, every k-th person is eliminated until one remains. Find the safe position.

# n=7, k=3
# People: 0 1 2 3 4 5 6
# Eliminate:  2, 5, 1, 6, 4, 0  →  survivor = 3
#
# josephus(7, 3) → 3

2. Solution 1 — Simulation O(n·k)

Use a list and simulate the elimination process. Clear but slow for large n.

def josephus_sim(n, k):
    people = list(range(n))
    idx = 0
    while len(people) > 1:
        idx = (idx + k - 1) % len(people)
        people.pop(idx)
        if idx == len(people):
            idx = 0
    return people[0]

print(josephus_sim(7, 3))  # 3

3. Solution 2 — O(n) Recursive Formula

After the first elimination, the problem reduces to a smaller Josephus problem on n-1 people. The recurrence maps survivor positions back to the original circle:

# J(1, k) = 0                          (only one person, position 0)
# J(n, k) = (J(n-1, k) + k) % n       (shift back by k each time we "unwrap" an elimination)

def josephus(n, k):
    pos = 0                          # survivor in 1-person circle
    for size in range(2, n + 1):
        pos = (pos + k) % size       # iterative version of recursion
    return pos

print(josephus(7, 3))   # 3
print(josephus(10, 2))  # 4  (0-indexed safe seat)

4. Solution 3 — Bit Rotation Trick (k=2 only)

When k=2 there's a famous O(1) formula based on bit manipulation. Write n in binary, rotate the leading 1 to the end.

def josephus_k2(n):
    # Find the highest power of 2 ≤ n
    highest_bit = 1
    while highest_bit * 2 <= n:
        highest_bit *= 2
    # Rotate leading 1 to the end: L = n - highest_bit, result = 2*L + 1 (1-indexed) or 2*L (0-indexed)
    L = n - highest_bit
    return 2 * L  # 0-indexed result

# Or with bit_length():
def josephus_k2_clean(n):
    p = n.bit_length() - 1        # position of leading 1
    L = n - (1 << p)               # strip the leading 1
    return (L << 1)                 # shift L left = rotate leading 1 to end

print(josephus_k2(10))  # 4  (matches O(n) formula)
print(josephus_k2(8))   # 0  (power of 2: survivor is at start)

5. Trace — O(n) Formula, n=7 k=3

# Start: pos=0 (survivor of 1-person circle)
#
# size=2: pos=(0+3)%2 = 1
# size=3: pos=(1+3)%3 = 1
# size=4: pos=(1+3)%4 = 0
# size=5: pos=(0+3)%5 = 3
# size=6: pos=(3+3)%6 = 0
# size=7: pos=(0+3)%7 = 3
#
# Survivor is at position 3  ✓