Pattern Reference
Josephus Problem
"Find the last remaining position when every k-th is eliminated. O(n) DP, O(k log n) for large n."
Loading...
Deep Dive Tutorial
Classic Josephus (k=2) has closed form J(n) = 2L + 1 where n = 2^m + L. General k: recurrence J(1,k) = 0 (0-indexed), J(n,k) = (J(n-1,k) + k) % n. This works because after eliminating the k-th person, we renumber the remaining n-1 people and solve the (n-1)-person problem. The offset +k maps from (n-1)-person numbering back to n-person numbering.
Josephus problem solutions
// O(n) mathematical solution (0-indexed position)
function josephus(n, k) {
let pos = 0; // survivor position in 1-person circle
for (let i = 2; i <= n; i++) {
pos = (pos + k) % i;
}
return pos; // 0-indexed: return pos+1 for 1-indexed
}
// O(n log n) simulation using order statistics (Fenwick tree)
// Returns full elimination order
function josephusOrder(n, k) {
const bit = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) updateBIT(bit, i, 1, n);
const order = [], alive = n;
let cur = 0; // current 0-indexed rank among alive
for (let i = 0; i < n; i++) {
cur = (cur + k - 1) % (alive - i); // 0-indexed rank of next to remove
const pos = findKth(bit, cur + 1, n); // 1-indexed actual position
order.push(pos);
updateBIT(bit, pos, -1, n);
// cur stays at same 0-indexed rank (now pointing to next person)
}
return order;
}Worked Problems
circle-help
Josephus formula derivation:
After eliminating person at position k (0-indexed), renumber remaining: person k+1 → 0, k+2 → 1, ..., so new_pos = (old_pos - k - 1 + n) % (n-1). Inverse: old_pos = (new_pos + k) % n. Apply from n=1 up.
k=2 closed form: Write n in binary as 2^m + L. Survivor = 2L + 1.
When to use O(n log n) simulation: When you need the full elimination order, not just the winner. Use a Fenwick tree or balanced BST to find the k-th remaining element in O(log n).
After eliminating person at position k (0-indexed), renumber remaining: person k+1 → 0, k+2 → 1, ..., so new_pos = (old_pos - k - 1 + n) % (n-1). Inverse: old_pos = (new_pos + k) % n. Apply from n=1 up.
k=2 closed form: Write n in binary as 2^m + L. Survivor = 2L + 1.
When to use O(n log n) simulation: When you need the full elimination order, not just the winner. Use a Fenwick tree or balanced BST to find the k-th remaining element in O(log n).