## 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:

1 2 3 4 |
0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0 |

Now look at the truth table of addition in binary:

1 2 3 4 |
0 + 0 = 0 (carry 0) 0 + 1 = 1 (carry 0) 1 + 0 = 1 (carry 0) 1 + 1 = 0 WITH CARRY 1 (=10) |

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.

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import java.util.*; public class Solution { public static void main(String[] args) { Scanner stdin = new Scanner(System.in); long n = stdin.nextLong(); String binary = Long.toBinaryString(n); long zeroes = 0L; for(int i = 0; i < binary.length(); i++) { if(binary.charAt(i) == '0') { zeroes++; } } if(n == 0L) { zeroes = 0; } long result = (long) Math.pow(2, zeroes); System.out.println(result); stdin.close(); } } |

## JavaScript

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
'use strict'; const processData = input => { const num = parseInt(input); const binary = num.toString(2); let zeroes = 0; for(let i = 0; i < binary.length; i++) { if(binary[i] === '0') { zeroes++; } } if(num === 0) { zeroes = 0; } const result = Math.pow(2, zeroes); console.log(result); }; process.stdin.resume(); process.stdin.setEncoding("ascii"); let _input = ""; process.stdin.on("data", input => _input += input); process.stdin.on("end", () => processData(_input)); |

## Scala

1 2 3 4 5 6 7 8 9 |
object SumVsXor extends App { val n = Source.stdin.bufferedReader().readLine().toLong val satisfied = Math.pow(2L, if(n == 0L) 0 else n.toBinaryString.count(_ == '0')).toLong println(satisfied) } |

## Ruby

1 2 3 4 5 6 7 |
n = gets.strip.to_i binary = n.to_s(2) zeroes = binary.count("0") zeroes = 0 if n == 0 result = 2**zeroes puts result |