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 <= 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 Streams with that many elements.


Show source
| java   | bit-manipulation   | algorithm   | java-stream   | xor   2017-01-04 15:01 2 Answers

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

  1. 2017-01-05 07:01

    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
    2the 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 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. 2017-01-08 07:01
        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);
       }
    

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

◀ Go back