Sum vs XOR

Hello World!

Let’s understand the Sum vs XOR problem on HackerRank. You may click on the title to read the problem statement. So let’s start.

Here, you may use brute force to iterate over x, 0 ≤ x ≤ n and if sum of x and n is equal to XOR or x and n, then increment the count. This takes O(n²) time and is inefficient for large values of n. Let’s see a more efficient solution.

Let two binary numbers be 1010 and 0100. Here, the sum and XOR of the above two numbers in equal. Did you notice something here? Consider first number. Whenever there is a “1” in first number, there is a corresponding zero in the second number. This is to avoid carry and maintaining sum equals XOR property. Also, whenever there is a “0” in the first number, it doesn’t matter whether there is a zero or a one in the corresponding position. The result will never lead to overflow.

Therefore, the count of numbers less than the number ’n’ whose sum and XOR are equal is 2^(number of zeroes). The number of ones won’t affect as their value of corresponding position in the second number would be fixed. All the numbers generated as such would be less than the given number ’n’. You may cross verify it.

Open for suggestions. The code for this problem in Python3 can be found here.

Happy coding…