## 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 `Stream`s.

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 <= 1015

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 `Stream`s with that many elements.

Show source

## Answers to Trying to find the number of x&#39;s that satisfies n + x = n ^ x fails with timeout ( 2 )

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 `Stream`s.

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 `0`s (marked with `~` above), since x must be <= `n`, so any leading `0`s 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
2the number of `0`s in `n`, not including leading `0`s.

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

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)
``````
2. ``````    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);
}
``````