Editorial for DMOPC '18 Contest 5 P1 - A Painting Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
We can recursively generate the binary representation of a number by appending the remainder of divided by 2 to the binary representation of divided by 2.
If we let represent the binary representation of , then we have:
After obtaining the binary representations, we can loop through the last characters, and count the number of positions with the same character, and print the answer.
Alternatively, if one is familiar with bitwise operations, this problem is the same as counting the number of bits set in .