3782. Last Remaining Integer After Alternating Deletion Operations

You are given an integer n.

We write the integers from 1 to n in a sequence from left to right. Then, alternately apply the following two operations until only one integer remains, starting with operation 1:

• Operation 1: Starting from the left, delete every second number.
• Operation 2: Starting from the right, delete every second number.

Return the last remaining integer.

class Solution {
public:
    long long lastInteger(long long n) {
        if(n <= 2) return 1;
        switch(n & 3) {
            case 0: return 4 * lastInteger(n / 4) - 1;
            case 1: return 4 * lastInteger((n + 3) / 4) - 3;
            case 2: return 4 * lastInteger((n + 2) / 4) - 3;
            case 3: return 4 * lastInteger((n + 1) / 4) - 1;
        }
        return -1;
    }
};