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.
The problem with your code is that it is very inefficient. For the case of
n==1000000000000000
, yourStream
pipeline is performing1,000,000,000,000,000
addition and XOR operations, which takes a long time. Testing for each number between 0 and n whethern + x == n ^ x
would take a long time even if you use a for loop instead ofStream
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 ton ^ x
,x
must have a0
value in all the bits corresponding with the1
bits ofn
(marked with=
above), and either0
or1
value in the bits corresponding with the0
bits ofn
(marked with-
above). This doesn't include the leading0
s (marked with~
above), since x must be <=n
, so any leading0
s inn
must also have a0
value inx
.This means that the total number of x's for which
n + x == n ^ x
is2the number of
0
s inn
, not including leading0
s.In the case of
n = 1000000000000000
, there are30
such0
bits, so the total number ofx
's that satisfy the requirement is 230.Here's one way to compute the total number of
x
's :