CircleRemoval

Original question

"Imagine you have a circle of people and you go around the circle removing every second person until one person is left.

If you have 3 people in the circle, then the 3rd person will be the last one remaining. If you have 4 people then the 1st person will be the last one remaining. If you have 11 people then the 7th person will be the one remaining.

If you have N people in the circle, who will be the last one remaining?

Please formulate your answer as a general solution and not as an algorithm that simulates the problem."

Logical analysis

Tested manually the process for several N to get a feel for the problem.

Always the first to go are the even-numbered people. This will bring the group to half of the original size and continue like this (removing half of the people on each pass) until a single person is left.

The order would be something like this: 1 1 3 1 3 5 7 1 3 5 7 9...

The number of the last person resets back to 1 every time that N hits a range of a new power of 2 (meaning it will need an additional pass through the circle) and then cycles through the odd-numbered people until the next power of 2 is reached.

Solution

N - number of people
L - number of the last person who will remain
P - highest power of 2 which fits in N
A - number of additional people between P and N

As I mentioned above, if N is a power of 2, then A is 0 and L will be 1. Considering this we can look at the problem from another angle: after A people have been removed we will have a circle of P people and the first one in this circle (the person next to the Ath which was removed) will be L.

This first pass only eliminates the even-numbered people so the last one standing will be 2A + 1.

This brings us to: