# Hackerrank – Sum vs XOR

## Hackerrank – Problem Statement

A description of the problem can be found on Hackerrank.

## Solution

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.