Now that I think about it, I should have just used bfs, typing code while someone is looking at you can cause brain to stop working :(

You can connect edges between two numbers satisfying either the operation 1 or operation 2.(Since there can be atmost two edges from a point)
And do this for all i <=1e5 then simply apply bfs from n.

Like you said, in an interview it makes sense to just do BFS and solve the problem that way. Interviews are not going to ask you about complicated algorithms.

But, since this is Codeforces... This question is asking you to convert a number from Gray code to binary, so something like this function should work (read the link for full explanation):

int GrayToBinary32(int num)
{
    num ^= num >> 16;
    num ^= num >>  8;
    num ^= num >>  4;
    num ^= num >>  2;
    num ^= num >>  1;
    return num;
}

There's a neat observation here that you missed.

So, in general, it takes you pow(2, K) operations to take you from pow(2, K) to pow(2, K-1).

And any number is nothing but the summation of powers of 2.

So, for 13 which is 1101 it'll take you Ans(1) + Ans(4) + Ans(8) operations to reach 0 :)

Isn't that the binary reflected gray of 8 . The problem is confusing but when I read it from 0000 to 1000 , the first four conversions made it clear .

I think I have this in my second year course this year , but it's not a coding subject though...

We can use dp. Let dp[k] = cost of erasing bit k if all other bits are 0. dp[k] = 2*dp[k-1]+1 (base: dp[0]=1). I will explain why.

If there is only one bit: Add a bit to its right, erase the left bit with operation 2 then erase the bit you added. This is equal to dp[k].

If there are more bits: You are trying to reach the leftmost bit by building bits(like a ladder). If there are some bits already, then it should be easier to reach the left most bit. Subtract the cost of right bits. The cost of some number N is = Cost(N) = dp[leftmost]-Cost(N-(1<<leftmost))

int dp[32];
int main() {
    int n;
    cin >> n;
    dp[0] = 1;
    for(int i = 1;i<n;i++)dp[i] = 2*dp[i-1]+1;
    int ans = 0, sign = 1;
    for(int i = 31;i > -1;i--){
        if(n & (1<<i)){
            ans += sign*dp[i];
            sign = -sign;
        }
    }
    cout << ans;
    return 0;
}