Hackerrank Solution: Sum vs XOR

Input Format

Constraints

• \(0\leq n\leq 10^{15}\)

Output Format

Print the total number of integer \(k\)'s satisfying both of the conditions specified above.

Solution

The core of this question addresses the way a half-adder works. A one bit addition in fact is XOR. The underlaying problem for this question is then to find out when a carry over happens, since this will change the result completely, which states that \(n + k=n\oplus k\) only holds for \(n\land k = 0\). We can also say that \(n+k=n\oplus k\Leftrightarrow n+k=n\lor k\), since \(n+k\geq n\lor k=n\oplus k+n\land k\). That means that all operands that are 1 in the bit vector \(n\) must be 0 in \(k\). The bits in \(n\) don't change, but \(k\) can take on 0 or 1. And that implies that all we need to do is counting the number of zeros in the bit vector \(n\), since they give answer to carry overs and how a combination with \(k\) will affect the result. Counting the number of unset bits can be accomplished with

\[\lfloor 1+\log n\rfloor - \sum\limits_{i=0}^{\lfloor \log n\rfloor} n_i = \sum\limits_{i=0}^{\lfloor \log n\rfloor} (1-n_i)\]

Implementing this mathematical derivation as a naive routine gives

def countZeroBits(n)
  c = 0;
  while n > 0
    c+= 1 - (n & 1)
    n>>= 1
  end
  return c
end

Okay, having the number of unset bits, how does this help? Since we want all numbers \(k\) for the criterion, it means that we need all possible permutations, leading to \(2^c\) being the solution:

def solve(n)
    1 << countZeroBits(n)
end

n = gets.strip.to_i
result = solve(n)
puts result