Hackerrank – Sum vs XOR

Hackerrank – Problem Statement

A description of the problem can be found on Hackerrank.


A mathematical trick.
just count total numbers of zero present in binary number of given n, and answer will be the 2 to the power of (total num of zero)

Look at the truth table of XOR:

Now look at the truth table of addition in binary:

This means the addition between two digits in binary is the XOR of the two bits, and the carry is the AND of the bits.
If you look for two operands A, B where A ^ B = A + B, you need that you never have a carry when summing them. This happens if it never happens that the i-th bit of A and the i-th bit of B are both 1. So given the operand A, all the bits in A which are 1 must be 0 in B. They are fixed bits and you have no choice for them. But all other bits in B are free and you can set them to 1 or 0 and the equation will keep being true. To count all possible values of B, you must then count the 0‘s in A (i.e. the number of free bits in B) and calculate 2 to the power of the free bits.

I created solution in:

All solutions are also available on my GitHub.





Leave a Reply

Your email address will not be published. Required fields are marked *