Josephus problem (recursion)
Medium TimeO(n) SpaceO(n)
People stand in a circle. Counting starts at the first of them and every kth person steps out, the count carrying on from the next person still standing, until one is left. Given n people and a step of k, both at least 1, return the survivor's position. Positions are numbered from 0 in the order they stand, and with one person the survivor is position 0.
Examples
Example 1
- Input
- n = 7k = 3
- Output
- Positions 2, 5, 1, 6, 4 and 0 leave in that order, and 3 is left standing.
3
Example 2
- Input
- n = 5k = 2
- Output
- Positions 1, 3, 0 and 4 leave in that order, and 2 is left standing.
2
The Code
function josephus(n, k) {
if (n === 1) return 0;
return (josephus(n - 1, k) + k) % n;
}
josephus(7, 3);Done
More like this
All recursion examples (13) →- Fibonacci The classic branching recursion — every call spawns two more.
- Factorial The simplest linear recursion — one call, one multiply.
- Tower of Hanoi Move a stack of disks by trusting the recursion for the rest.
- GCD (Euclid) Euclid’s algorithm — recursion that shrinks fast.
- Power Raise a number to a power one multiply at a time.
- Sum of digits Peel one digit off at a time with the modulo trick.