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

class Solution {
public:
    int lastRemaining(int n) {
        int l = 1, r = n, jump = 1, toLeft = 1;
        while(l != r) {
            if(toLeft) {
                toLeft = 0;
                
                l = l + jump;
                jump<<=1;
                r = l + (r - l) / jump * jump;
            } else {
                toLeft = 1;
                
                r = r - jump;
                jump <<= 1;
                l = r - (r - l) / jump * jump;
            }
        }
        
        return l;
    }
};