4
\$\begingroup\$

This problem is from HackerRank (not a competition, just for practice)

Basically what you do is take in two integers as a range and then finding the maximum XOR from a pair of integers in that interval.

Here is my code for doing so (it passed all the test cases):

static int maxXor(int l, int r) {
    int maxXor = l ^ r;
    for(int left=l;left<=r; left++) {
        for(int right=l;right<=r; right++) {
            if((left ^ right) > maxXor) {
                maxXor = left ^ right;
            }
        }
    }
    return maxXor;
}

I was able to tell that this code segment runs in \$\mathcal{O}(n^2)\$ because the outer for loop will run in \$\mathcal{O}(N)\$, \$N\$ as in number of integers in the range, and the inner loop will also run in \$\mathcal{O}(N)\$. Because each time the outer loop runs, the inner loop runs one time aswell, the entire code segment will in \$\mathcal{O}(N^2)\$. Is that good analysis?

But anyways, is there an optimization (for performance) for this code segment to get the runtime down to \$\mathcal{O}(N)\$ or \$\mathcal{O}(log N)\$ perhaps?

\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

You are correct that your code has \$\mathcal{O}(n^2)\$ performance.

Here is a solution in \$\mathcal{O}(log(n))\$:

static int maxXor(int l, int r) {
    int c = 0;
    int exp = 0;
    while (l != 0 || r != 0) {
        c++;
        if ((l & 1) != (r & 1)) {
            exp = c;
        }
        l >>= 1;
        r >>= 1;
    }
    return (1 << exp) - 1;
}

Explanation

The task of finding the maximum XOR value \$m\$ is equivalent to finding the most significant bit \$b\$ that differs between L and R. The maximum XOR value will be \$m=2^{b+1}-1\$.

Proof sketch

Let's use the number 42 (101010) and 59 (111011) as a running example. The most significant bit that differs is bit 4, therefore we expect \$m=31\$.

vvvvvv all these bits are equal
00000101010
00000111011
      ^ bit b=4 differs

Note that bits above \$b\$ never change when counting from L to R, and since XOR only cares about different bits we have \$m<2^{b+1}\$ as an upper bound.

But since bit \$b\$ is set in R and not set in L, there have to be two numbers in the range [L, R] where:

  • In the first number x, all bits below \$b\$ are set.
  • In the second number x+1, \$b\$ is set, but all bits below it are not.

So x XOR x+1 will be equal to the sum of all bits up to and including \$b\$ which is \$2^{b+1}-1\$, i.e. \$m \geq 2^{b+1}-1\$.

Thus we have \$2^{b+1}-1 \leq m < 2^{b+1}\$

=> \$m = 2^{b+1}-1\$

In the example:

47 101111
48 110000
47 XOR 48 = 31
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.