Elimination Game
You have a list arr of all integers in the range [1, n] sorted in a strictly increasing order. Apply the following algorithm on arr:
- Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
- Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
- Keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Given the integer n, return the last number that remains in arr.
Example 1
Input
n = 9Output
6After alternating eliminations, the sequence becomes [2, 4, 6, 8], then [2, 6], then [6], so 6 remains.
Example 2
Input
n = 1Output
1The list contains only 1, so 1 is the last remaining number.
Constraints
- 1 <= n <= 10^9