Elimination Game
You are given the integers from 1 to n arranged in a list. A game proceeds in rounds as follows:
- First round: remove every other number from left to right, starting with the first number. The first number (1) is removed, the second (2) is kept, the third (3) is removed, the fourth (4) is kept, and so on.
- Second round: with the remaining numbers, remove every other number from right to left, starting with the rightmost number. The rightmost number is removed, the next one to its left is kept, and so on.
- Continue alternating directions until only one number remains.
Return the last remaining number.
Examples
Input: 1
Output: 1
Input: 6
Output: 4
Hints
Simulating the process directly for large n is too slow. Think about how the remaining numbers transform after each round. What happens to the step size between surviving numbers?
After one round of elimination from left, only the odd numbers remain: 1, 3, 5, ... These can be expressed as 2 × i - 1 for i = 1 to ceil(n/2). Keep track of the first surviving number and the step size.
Use a variable to track the current step size (doubles each round). Whether the first element survives depends on the parity of the remaining count and the direction of elimination. Maintain a `head` variable that stores the first remaining number.
Related Problems
Elimination Game
You are given the integers from 1 to n arranged in a list. A game proceeds in rounds as follows: