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)