We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

Strip your number down to the most significant bit followed by some amount of 0s or 1s thereafter. This can be done using l^r. The first time one of the numbers has a 1 and the other doesn't, this will be your most significant bit.

Set all the following 0s to 1s. If 1000 is your most significant, the maximum will be 1111.

Print the decimal interpretation of the resulting binary number.

8 is 1000 and 7 is 0111. Anything between 8 and 0 is going to be 15 because your highest XOR number is 1111. As you can see, you can find this by finding the most significant bit and flipping all the following to 1.

8 is 1000 and 9 is 1001. Here you'll find that the answer is 0001. This is because 8 and 9 share the same most significant bit. So after XOR the most significant bit is 0001.

27 is 11011 and 8 is 01000. Here your MSB is 10000 and you can choose 10111 and 01000.

I wish I could explain it better but it's easiest to notice the pattern and go from there. Every answer will always be a power of 2 minus 1, so every answer is always a series of 1s.

The idea in my example is to use the processor instruction that does this in hardware. Of course, it depends on the specific processor brand, type and model how fast the hardware implementation actually is. (or if such instruction exists at all)

Although your code is O(1), any O(b) solution will be of the same complexity or perhaps even faster for cases where b < 4. Here b is the index of MSB in a^b.

A very simple O(b) solution that will work for any values of L & R and will work faster than above code for cases where b < 4

Nice solution. How does one deduce a solution like this ?

Before peeking into the discussion forum, I was thinking that if l is 0 then the answer would be r ^ 0 = r. Hence, when l is not 0 the answer should have something to do with r ^ l. But I could not take my thought process any further.

For me what works is taking a few examples and trying to find a pattern. Once I find a pattern, I convince myself that it will work for all cases or try to find a test case that will fail. Once I find a test case that fails I'll try to modify the pattern or come up with a new pattern. Like in this case the pattern was the MSB that differs between the two numbers. Hope this helps.

Time complexity is O(n);
Ex:1 2 3 4 5 l=1 and r=5
property:Ex-or operations commutative.
1@2 2@4 3@4 4@5
1@3
1@4
1@5
first time,it take n-1 @(ex-or) operation and after that only 1 for each input

## Maximizing XOR

You are viewing a single comment's thread. Return to all comments →

Question should be with strict time limit

I wonder if there's an algorithm to compute it in faster than O(n^2) time.

It is possible to make a solution

`O(b)`

where`b`

is the position of the most significant bit of`R`

Hint:

`L=7,R=8`

, andmostSignificantBit.Is this considered constant time? I think so.

No, it is not, it's actually

`O(log2(R))`

, finding the most significant bit is not constant.I was just a bit naive, and didn't see that in my case

`b = f(R) = log2(R)`

Could you give us more content about this solution?

Thanks!

sir can you explain how the below solution is solving this problem.

def maxXOR(L,R): P = L^R ret = 1 while(P): # this one takes (m+1) = O(logR) steps ret <<= 1 P >>= 1 return (ret - 1)

i dont understand that how we are getting right answer by doing this method.

Consider this: https://www.hackerrank.com/challenges/maximizing-xor/submissions/code/44305239

Thanks buddy for response.But can you explain why we are replacing all zeros to ones after most significant digit.

The best way I can explain it is with examples.

8 is 1000 and 7 is 0111. Anything between 8 and 0 is going to be 15 because your highest XOR number is 1111. As you can see, you can find this by finding the most significant bit and flipping all the following to 1.

8 is 1000 and 9 is 1001. Here you'll find that the answer is 0001. This is because 8 and 9 share the same most significant bit. So after XOR the most significant bit is 0001.

27 is 11011 and 8 is 01000. Here your MSB is 10000 and you can choose 10111 and 01000.

I wish I could explain it better but it's easiest to notice the pattern and go from there. Every answer will always be a power of 2 minus 1, so every answer is always a series of 1s.

I think it can be O(logR) complexity.

It can be better than log(R). If R and L are 4 byte integers, it can be done in 31 steps worst case.

No, it's not worse, it's the same.

What you are saying is

`log2(R)`

.in computer science, log(n) means log2(n)

lg(n) means log2(n), log(n) means log10(n). usually

no it is not

doesn't matter, logs of any base are big-O equivalent

I have it in constant O(1) time here:

https://www.hackerrank.com/challenges/maximizing-xor/forum/comments/46432

c++, same complexity, but probably faster on newer processors, although not directly portable:

How does a compiler compute 'number of leading zeros' in O(1)? I think this solution is O(b) where b is the index of MSB in a^b

The idea in my example is to use the processor instruction that does this in hardware. Of course, it depends on the specific processor brand, type and model how fast the hardware implementation actually is. (or if such instruction exists at all)

Although your code is O(1), any O(b) solution will be of the same complexity or perhaps even faster for cases where b < 4. Here b is the index of MSB in a^b.

A very simple O(b) solution that will work for any values of L & R and will work faster than above code for cases where b < 4

Nice solution. How does one deduce a solution like this ?

Before peeking into the discussion forum, I was thinking that if l is 0 then the answer would be r ^ 0 = r. Hence, when l is not 0 the answer should have something to do with r ^ l. But I could not take my thought process any further.

For me what works is taking a few examples and trying to find a pattern. Once I find a pattern, I convince myself that it will work for all cases or try to find a test case that will fail. Once I find a test case that fails I'll try to modify the pattern or come up with a new pattern. Like in this case the pattern was the MSB that differs between the two numbers. Hope this helps.

Can you please explain how you came up with this soultion. Thanks :)

editorial

Time complexity is O(n); Ex:1 2 3 4 5 l=1 and r=5 property:Ex-or operations commutative. 1@2 2@4 3@4 4@5 1@3 1@4 1@5 first time,it take n-1 @(ex-or) operation and after that only 1 for each input

https://cs.stackexchange.com/questions/29508/finding-the-max-xor-of-two-numbers-in-an-interval-can-we-do-better-than-quadrat

Solution in O(g) time, where g is the MSF of (l xor r). For a 32 bit unsigned integer, worst-case g would be 32 operations.