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

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 <= 10
^{15}

Sample Input:5

Sample Output:2

Explanation:For

n = 5, thexvalues0and2satisfy the conditions:

- 5 + 0 = 5 ^ 0 = 5
- 5 + 2 = 5 ^ 2 = 7
Thus, we print

2as our answer.

Sample Input:10

Sample Output:4

Explanation:Forn = 10, thexvalues0,1,4, and5satisfy 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

4as 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 ( 2 )

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 isIn 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`

is2

^{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^{30}.Here's one way to compute the total number of

`x`

's :