100 people in a circle, every second one leaves.
The Josephus problem: 100 people stand in a circle, every second person is eliminated going round and round, and you want to be the last one standing. Which position do you choose? Simulation gives 73. The interview wants the formula, and it is a binary rotation.
One hundred people stand in a circle, numbered 1 to 100 clockwise. Starting from person 1, you count around the circle and eliminate every second person: person 2 leaves, then person 4, then 6, and so on. When you reach the end of the circle you keep going with whoever remains, always removing the next person after the one you skipped. This continues until one person is left.
Which position survives? And can you give the answer for any circle size without simulating?
Simulating 100 people by hand is tedious but possible, and a program does it in a millisecond. Neither is the point. The question interviewers care about is the second one, and it has a beautiful answer. Start with small circles, write down the survivor for each size from 1 up to 16, and stare at the results next to their binary representations. The pattern is there.
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
For circle sizes 1 through 8 the survivors are 1, 1, 3, 1, 3, 5, 7, 1. Whenever the size is a power of two, the survivor is person 1. Why?
Hint 2 the key move
Write the size as a power of two plus a remainder: n equals 2 to the power m, plus L. After L eliminations, exactly a power of two remain, and the count is about to start from a known person. Who is standing there?
Hint 3 nearly the answer
After L eliminations the next person to be skipped is number 2L plus 1, and a power-of-two circle always returns to the person the count starts from. So the survivor is 2L plus 1. Compute L for 100.
The solution
Reveal the full solution
Position 73.
Two facts do all the work. First, if the circle size is exactly a power of two, the person who starts the count survives: after one full pass, every second person is gone, the size is halved, still a power of two, and the count resumes from the same person, so by induction they are never eliminated. Second, for any size n, write n as 2 to the power m plus L, where 2 to the power m is the largest power of two not exceeding n. After L people have been eliminated (persons 2, 4, up to 2L), exactly 2 to the power m people remain, and the count is about to begin from person 2L plus 1. By the first fact, that person survives.
For n equals 100: the largest power of two below 100 is 64, so L is 36, and the survivor is 2 times 36 plus 1, which is 73.
The binary view is the same answer in a form you can compute in your head. Write n in binary, move its leading 1 bit to the end, and read the result: 100 is 1100100 in binary; rotating the leading 1 to the end gives 1001001, which is 73. This works because removing the leading bit leaves L, and appending a 1 bit computes 2L plus 1.
| n | n in binary | Rotate leading 1 to the end | Survivor |
|---|---|---|---|
| 5 | 101 | 011 | 3 |
| 8 | 1000 | 0001 | 1 |
| 13 | 1101 | 1011 | 11 |
| 100 | 1100100 | 1001001 | 73 |
What this puzzle is really testing
Whether you reduce a process to a recurrence and then solve the recurrence, rather than simulating. The general recurrence for eliminating every k-th person is J(n) equals (J(n minus 1) plus k minus 1) mod n plus 1, which is a one-line loop in O(n) time and works for any k; the closed form above is what falls out when k is 2. Recognising that a power-of-two case is the base and everything else reduces to it is the same structural move as in the Tower of Hanoi, and the reduce-to-a-smaller-instance habit is developed in recursion as induction. The circular elimination itself is a standard exercise in circular linked lists, where simulation costs O(n) per elimination unless you use the recurrence.
Follow-ups to expect
Every third person instead of every second: no clean closed form, but the O(n) recurrence handles it. Which position survives second to last? Same recurrence, stop one step earlier. And the story behind the name: Josephus, a first-century historian, reportedly used this calculation to be the last survivor of a suicide pact and then surrendered instead, which interviewers occasionally mention to check whether you recognise the problem by name.