Need help solving codeforces problem - contest 1152

1

Problems
Usually I’m able to solve only 1 or sometimes two problem during codeforces contests, I tried
solving by reading their editorials but they are really small and sometime doesn’t even make sense to me.
If someone else here on codechef, regularly participates in div 2 round then please share your problems approach with me.

I’m currently stuck on this problem

1 Like
2

It always uses 39 steps

j=19;
while(j--){
    k=(int)log2(n)+1;
    n^=(int)pow(2,k)-1;
    n++;
    cout << k <<' ';
}

cout << (int)log2(n)+1;

above code is trying to make it 0…
what I mean is if number is 11_{10} == 1011_2
then I make it
(1011_2 \oplus 1111_2) == 100_2 -> 101_2
(101_2 \oplus 111_2) == 10_2 -> 11_2
(11_2 \oplus 11_2) == 00_2 -> 1_2 (done and works for almost all numbers !!)

the above algorithm will always give a number which is 2^n (n>=0)
(why ? because it is the only n when it stucks into infinite loop of being 2^n-1 and then 2^n )
now
suppose n=8_{10} = 1000_2
1000_2 \oplus 1111_2 == 0111_2 (done)

2 Likes
3

what log2(n) actually does? specifically why k = (int)log2(n) + 1

4

(int)log2(n) finds the position of the right most bit in 0-index form…
Suppose number is
10110_2 then (int)log2(n)=4
Now
2^{4+1}= 2^5 = 100000_2
And now,
2^5-1 = 011111_2
Actually the algorithm is keep Xoring it with a number which has all bits 1
10101_2 then Xor it with 11111_2
Now you find your way of Xoring it with 11111_2 in code… :slight_smile: