The Josephus problem
41 people stand in a circle, numbered 1 to 41. Going round the circle, every second person is removed: first person 2, then 4, then 6, and so on, wrapping around, until one person remains.
Which number is left? Can you find a formula?
Show hint
Try small circles (1 to 8 people) and look for a pattern. What happens when the number of people is a power of 2?
Show solution
Person 19.
When the number of people is a power of 2, person 1 always survives. Otherwise, write n = 2m + L with 2m the largest power of 2 not above n. After L removals there are exactly 2m people left, and the person about to start the next round survives. That person is 2L + 1.
For 41: 41 = 32 + 9, so the survivor is 2 × 9 + 1 = 19. A ten-line simulation with a list or collections.deque confirms it.
Want a problem like this every day? See today's problem and keep a streak going.