Elimination Game -- LeetCode

[Question]

There is a list of sorted integers from 1 to n. 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 right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

[Analysis]
The value of the last remaining number is equal to the position of that number in the original array. Think the process in backward: assume x is in position i in round n, then what is the position of x should be in the previous round n-1?
     1) If n-1 is odd, the x must be in 2*i position in round n-1.
     2) If n-1 is even, and the count of  number in round n-1 is even, the position of  x must be in 2*i-1 in round n-1.
     3) If n-1 is even, and the count of number in round n-1 is odd, the position of x must be in 2*i in round n-1.

Therefore, we can trace backward from position 1 (last remaining) to the position of the number in original array. The time complexity is O(Log N), the space complexity is O(Log N) -- space can be reduced to O(1) as it is only needed for the count of numbers in each round.

[Solution]
class Solution {
public:
    int lastRemaining(int n) {
        int res = 1;

        stack<int> nums;
        while (n>1) {
            nums.push(n);
            n/=2;
        }
        while (!nums.empty()) {
            if (nums.size() % 2==0 && nums.top()%2==0)
                res = res*2-1;
            else
                res *=2;
            nums.pop();
        }
        return res;
    }
};