Hackerrank - Sum vs XOR - Pavol Pidanič

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:

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

0 ^ 0 = 0

0 ^ 1 = 1

1 ^ 0 = 1

1 ^ 1 = 0

Now look at the truth table of addition in binary:

0 + 0 = 0 (carry 0)
0 + 1 = 1 (carry 0)
1 + 0 = 1 (carry 0)
1 + 1 = 0 WITH CARRY 1 (=10)

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:

Scala
Java
JavaScript
Ruby

All solutions are also available on my GitHub.

Java

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();
    }
}

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

'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));

'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

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)
}

object SumVsXor extends App {

val n = Source.stdin.bufferedReader().readLine().toLong

val satisfied = Math.pow(2L, if(n == 0L)

else

n.toBinaryString.count(_ == '0')).toLong

println(satisfied)

}

Ruby

n = gets.strip.to_i
binary = n.to_s(2)
zeroes = binary.count("0")
zeroes = 0 if n == 0
result = 2**zeroes

puts result

n = gets.strip.to_i

binary = n.to_s(2)

zeroes = binary.count("0")

zeroes = 0 if n == 0

result = 2**zeroes

puts result

Pavol Pidanič

I can count to 1023 with 10 fingers

Hackerrank – Sum vs XOR