n people stand in a circle, numbered 0 through n - 1. Starting the count at person 0, count forward k people around the circle (wrapping past the end back to the start) and eliminate whoever the count lands on. Counting for the next elimination resumes with the person immediately after the one just removed.
Keep eliminating one person every k count until a single person is left. Return that survivor's original 0-indexed position.
For example, with n = 5 and k = 2: circle is [0, 1, 2, 3, 4]. Counting 2 from person 0 lands on person 1 — eliminate them. Counting 2 from person 2 lands on person 3 — eliminate them. Counting 2 from person 4 wraps to person 0 — eliminate them. Counting 2 from person 2 lands on person 4 — eliminate them. Person 2 is the sole survivor.
Example
Eliminations happen in order 1, 3, 0, 4; person 2 survives.
Constraints
- 1 <= n <= 10^5
- 1 <= k <= 10^5
Intuition
A first pass just simulates the circle literally: keep an array of everyone still standing, and repeatedly compute the index the next count of k lands on, removing that person, until only one remains.
function josephusProblem(n, k) {
// Track everyone still standing, indexed by their original position.
const circle = Array.from({ length: n }, (_, i) => i);
// "current" always points at the position where the next count of k starts.
let current = 0;
while (circle.length > 1) {
// Count k people starting at current (current itself is count 1),
// wrapping past the end of the (shrinking) circle back to the front.
current = (current + k - 1) % circle.length;
// Remove the eliminated person; every later element shifts down by one.
circle.splice(current, 1);
// current already points at the next person to start counting from.
}
// One person remains — their original position is the answer.
return circle[0];
}Every elimination removes one element from an array, which is O(n) work on its own (everything after it has to shift down), and there are up to n - 1 eliminations — O(n²) total. Can we do better?
Key observation: solving the elimination for n people is really just solving it for n - 1 people, then correcting for the one extra person who joined the circle. If we already know the survivor's position J(m - 1) in a circle of m - 1 people, adding one more person and re-running the exact same k-counting rule shifts everyone's numbering by the same amount — the survivor's position in the m-person circle is always (J(m - 1) + k) mod m. That's the same bottom-up recurrence idea behind Dynamic programming: solve the smallest subproblem first (a circle of one person trivially survives at position 0) and build the answer up to the full size, one person at a time, without ever touching an array.
In the stored solution this collapses to a single running variable, survivor, updated once per iteration of people from 2 up to n — the same names used below.
Walking it through:
n = 5, k = 2 — rebuilding the survivor from a 1-person circle up to 5
Base case: a circle of one person needs no elimination — they trivially survive at position 0.
Grow to 2 people: the previous survivor's position shifts by k (=2), wrapped mod the new circle size.
Growing to 3 people finally moves the survivor away from position 0.
At 4 people the shift wraps back around to 0 — the mod is doing real work here, not just adding.
The circle reaches its full size of 5 and the recurrence returns 2 — the same survivor a full hand simulation of the eliminations (1, 3, 0, 4) produces.
n = 4, k = 6 — k larger than the circle itself; the mod folds the wraparound in for free
Base case, same as always: one person needs no elimination.
k (=6) is three times the circle size, but the mod folds the extra laps in automatically — no special-casing k > people needed.
Still 0 — the running survivor hasn't had to move yet at this size.
At the full circle of 4 the same formula lands on position 2 — matching a hand simulation where the count of 6 wraps a full lap of 4 plus 2 more before each elimination.
Optimization
Iterative recurrence (unwind the recursion)
The recursive Josephus recurrence says: with 1 person, the survivor is trivially position 0. Going from m - 1 people to m people (adding one more person to the circle and re-running the same elimination rule), the survivor's position shifts by k positions (mod m) relative to the smaller circle's survivor: J(m) = (J(m - 1) + k) mod m.
Unwinding that recurrence from m = 2 up to m = n avoids recursion overhead and stack depth entirely.
O(n) time, O(1) space.
function josephusProblem(n, k) {
// J(1) = 0: with one person left, they trivially survive.
let survivor = 0;
// Rebuild the answer for circles of size 2, 3, ..., n from the smaller circle's survivor.
for (let people = 2; people <= n; people++) {
survivor = (survivor + k) % people;
}
return survivor;
}Direct simulation
Track the circle as a list of remaining original positions and a current count-start index. Repeatedly compute the eliminated index as (current + k - 1) mod circle.length, remove that person, and resume counting from the same index (which now points at the next survivor after the removal).
O(n²) time in the worst case (each removal from an array is O(n)), O(n) space — correct, but too slow for the largest inputs.
function josephusProblem(n, k) {
const circle = Array.from({ length: n }, (_, i) => i);
let current = 0;
while (circle.length > 1) {
// The kth person counted from "current" (current itself counts as 1).
current = (current + k - 1) % circle.length;
circle.splice(current, 1);
}
return circle[0];
}Complexity analysis
Time complexity: O(n). Here's why:
- The loop runs once for each circle size from
2up ton— exactlyn - 1iterations. - Each iteration does O(1) work: one addition, one modulo, one assignment — no inner loop and no array operation.
So the total time is (n - 1) × O(1) = O(n) — a strict improvement over the O(n²) array simulation, and asymptotically optimal, since the survivor genuinely depends on the shift at every circle size from 1 up to n.
Space complexity: O(1). Here's why:
- Only a single running scalar,
survivor, carries information from one iteration to the next. - Unlike the brute-force simulation, no array holding all
npeople is ever built.
So the extra space is O(1), regardless of how large n gets — a strict improvement over the brute force's O(n) circle array.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| n = 1, k = 1 | 0 | Smallest possible circle — one person survives with no eliminations at all. |
| n = 2, k = 5 | 1 | Two people; k's parity (here odd) is all that matters — 5 mod 2 behaves just like k = 1. |
| n = 4, k = 1 | 3 | k = 1 always eliminates the immediately-next person in order, so the last person standing is always index n - 1. |
| n = 5, k = 12 | 2 | k (12) far exceeds the circle size at every step — the mod folds the extra laps in without any special-casing. |
| n = 9, k = 4 | 0 | A moderate circle where the survivor lands back at the very first position, even though person 0 isn't eliminated first. |
Try it yourself
Write your solution against the real judge before checking the reference.