## Editorial for DMOPC '18 Contest 5 P1 - A Painting Problem

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

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.

**Time Complexity:**

Alternatively, if one is familiar with bitwise operations, this problem is the same as counting the number of bits set in .

**Time Complexity:**

## Comments

For the bitwise operations solution, why isn't the time complexity the same as the recursive solution? Doesn't bitwise XOR have a time complexity of O(logN)?

Bitwise XOR is O(1).