Sign in to watch this lesson
Advanced - Combinatorics, Games and Puzzles Ā· 4:00
The Josephus Problem
People stand in a circle and every k-th one is removed until one is left. Instead of simulating, we relabel the circle after the first removal and get the recurrence J(n) = (J(n-1) + k) mod n, which runs as a single loop in linear time and constant memory. For k = 2 the survivor has a closed form, two times the distance past the largest power of two, plus one.
You will learn
- Simulate the Josephus game and state the cost of array, linked-list and order-statistic-tree simulations
- Derive J(n) = (J(n-1) + k) mod n by relabelling the circle after the first removal, with positions counted from 0
- Implement the survivor as an iterative O(n), O(1)-memory loop, avoiding the 0/1-indexing bug and recursion depth
- Use the k = 2 closed form J(n) = 2(n - 2^floor(log2 n)) + 1 and explain why survivors restart at powers of two