Last one remaining in the circle

The problem

"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."

The solution

Well, firstly we can affirm that an even number (divisible by two) will never be the last one remaining, due to the fact that all of them will be removed on the first iteration.

Starting from 4 people and less than 8 in the circle, we can notice that the position of the person who lastly leaves the circle increases +2 starting from 1st (i.e., the next odd number). After that, I mean greater and equal than 8 people and less than 15, the position of who will leave lastly restarts from 1st and goes on.

So, the quickest way to say who will be the last one reamaining is to divide in two options, according to the answer for this question: "Is the N a power of 2 (e.g., 2, 4, 8, 16, 32, etc)?": Option 1: Yes, it is. So, certainly we can affirm that the 1st person will be the last one remaining. Option 2: No, it is not. So, we simply need to use the greatest power of 2 and less than N to call it as X. Finally, we apply those values into the formula [(N - X) * 2] + 1 and the result of it will be the position of the last person remaining.

Example: N = 12. So, the greatest power of 2 and less than 12 is 8. Therefore, X = 8. Applying these values into the formula we get [(12 - 8) * 2] + 1 = 9. The 9th person will be the one remaining.

Built With

• logical-thinking