Trying to find the number of x's that satisfies n + x = n ^ x fails with timeout

Question

I'm trying to solve the following problem from the section Bit Manipulation at the Hacker Rank site using new features of Java 8 such as Streams.

The problem description:

Given an integer, n, find each x such that:

• 0 <= x <= n
• n + x = n ^ x

where ^ denotes the bitwise XOR operator. Then print an integer denoting the total number of x's satisfying the criteria above.

Constraints

• 0 <= n <= 10¹⁵

Sample Input: 5

Sample Output: 2

Explanation:

For n = 5, the x values 0 and 2 satisfy the conditions:

• 5 + 0 = 5 ^ 0 = 5
• 5 + 2 = 5 ^ 2 = 7

Thus, we print 2 as our answer.

Sample Input: 10

Sample Output: 4

Explanation: For n = 10, the x values 0, 1, 4, and 5 satisfy the conditions:

• 10 + 0 = 10 ^ 0 = 10
• 10 + 1 = 10 ^ 1 = 11
• 10 + 4 = 10 ^ 4 = 14
• 10 + 5 = 10 ^ 5 = 15

Thus, we print 4 as our answer.

My code is as follows:

public class SumVsXor 
{
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long count = LongStream.rangeClosed(0, n)
                               .filter(k -> k + n == (k ^ n))
                               .count();
        System.out.println(count);  
    }
}

The problem is this code doesn't pass all the test cases.

It works for small values of n, but for large values such as 1000000000000000 it fails due to timeout.

I wonder whether LongStream can't handle Streams with that many elements.

Answer 1

The problem with your code is that it is very inefficient. For the case of n==1000000000000000, your Stream pipeline is performing 1,000,000,000,000,000 addition and XOR operations, which takes a long time. Testing for each number between 0 and n whether n + x == n ^ x would take a long time even if you use a for loop instead of Streams.

Instead of checking all the numbers between 0 and n, you should try to figure out a better way to calculate the required total number of x's. That fact that this problem appears under a "Bit Manipulation" section should give you a hint to look into the bits of numbers that satisfy
n + x == n ^ x.

Let's consider the case of n==1000000000000000. The binary representation of that large number is

0000000000000011100011010111111010100100110001101000000000000000
              ===   == = ====== = =  =  ==   == =
                 ---  - -      - - -- --  ---  - ---------------
~~~~~~~~~~~~~~              

In order for n + x to be equal to n ^ x, x must have a 0 value in all the bits corresponding with the 1 bits of n (marked with = above), and either 0 or 1 value in the bits corresponding with the 0 bits of n (marked with - above). This doesn't include the leading 0s (marked with ~ above), since x must be <= n, so any leading 0s in n must also have a 0 value in x.

This means that the total number of x's for which n + x == n ^ x is
2^{the number of 0s in n, not including leading 0s}.

In the case of n = 1000000000000000, there are 30 such 0 bits, so the total number of x's that satisfy the requirement is 2³⁰.

Here's one way to compute the total number of x's :

long n = 1000000000000000L;
int zeroBitsCount = 0;
while (n > 0) {
    if (n % 2 == 0) {
        zeroBitsCount++; // counts the number of non-leading 0 bits
    }
    n = n >> 1; // divide n by 2 in order to examine the next bit in the next iteration
}
long total = 1L << zeroBitsCount; // the total is 2^(the 0 bits count)

Answer 2

I came to the same result, but via a different explanation, so thought I might post it here.

Eran's answer got to the same conclusion that I did : to modify the zeroes in the binary representation of the initial number - that is pretty straightforward.

Let's suppose our number is

101010100

so it has 5 zeroes.

you need all the possible combinations of:

• a single zero
• two zeroes
• three zeroes
• four zeroes
• five zeroes

that is actually :

 comb(1,5) + comb(2,5) + comb(3,5) + comb(4,5) + comb (5,5)

that is a well known formula being equal to:

pow(2,n) // where n is five in our case

from there the solution is obvious...

Answer 3

This is a simple question if you know little bit about XOR. I don't know much about java. But I can explain in python.

1.First convert the number to binary. 2.Count the number of zeros in that binary number. 3.print 2 ^ (number of zeros) and that's it.

Here is my python code.

n = int(input())
sum = 0
if n!=0:
    n=str(bin(n))
    for i in range(len(n)):
            if n[i]=='0':
           sum = sum + 1
    print(2**(sum-1))
else: print(1)

The reason to decrement the sum by 1 is, in python it convert the number to the binary as this format. e.g: 0b'10101.

Answer 4

public static void main (String[] args) {
    Scanner in = new Scanner (System.in);
    long n = in.nextLong();
    long count = 1L << (64-Long.bitCount(n)-Long.numberOfLeadingZeros(n));
    System.out.println(count);
}