# Maximizing XOR

# Maximizing XOR

RodneyShag + 26 comments ### Java solution - more efficient than Editorial solution

import java.util.Scanner; public class Solution { public static void main(String [] args) { Scanner scan = new Scanner(System.in); int L = scan.nextInt(); int R = scan.nextInt(); scan.close(); int xored = L ^ R; int significantBit = 31 - Integer.numberOfLeadingZeros(xored); int result = (1 << (significantBit + 1)) - 1; System.out.println(result); } }

To maximize A xor B, we want A and B to differ as much as possible at every bit index.

We first find the most significant bit that we can force to differ by looking at L and R.

For all of the lesser significant bits in A and B, we can always ensure that they differ and still have L <= A <= B <= R.

Our final answer will be the number represented by all 1s starting from the most significant bit that differs between A and B

### Let's try an example

L = 10111 R = 11100 _X___ <-- that's most significant differing bit 01111 <-- here's our final answer

Notice how we don't directly calculate the values of A and B.

From my HackerRank solutions.

nm1511 + 0 comments pro!

I0000 + 1 comment Nice solution :)

Abhishek_G0YAL + 2 comments # Here is a one liner in C++

int maximizingXor(int l, int r) { return (1 << int(log2(l ^ r) + 1)) - 1; }

sanjeevbittu83 + 1 comment can you explane it

shantamshrestha + 0 comments I tried this code. It passed all test cases but, when I try inputs l = 10 and r =10, it gives me an output 1. Shouldn't it be 0?

snaran + 0 comments My way had the same concept as your picture: to calculate the highest order bit that is different and subtract one from it, though my way has a loop that you avoided by doing an ^.

static int maxXor(int l, int r) { int lBit = Integer.highestOneBit(l); int rBit = Integer.highestOneBit(r); if (lBit == rBit) { if (lBit == 0) { return 0; } else { int newL = l & (~lBit); int newR = r & (~lBit); return maxXor(newL, newR); } } else { int max = Math.max(lBit, rBit); return (max << 1) -1; } }

watsaqat + 2 comments I just want to say, I wrote about 75 lines of code because I did not know about the integer bitwise operator ^. I did learn alot though doing everything from scratch :D ...

uni691125 + 0 comments [deleted]kunj07soni + 0 comments Yeah wrote 50 line in python and found one line solution here.. :(

R101154 + 7 comments I'm getting a wrong answer on test case 1. I looked at the test case and when I copy and paste the test case in myself -- it works just fine. All other test cases run just fine without any errors.

I believe there is something wrong with the test.

kokabi + 2 comments Me Too!

eagle31337 + 1 comment Check range =)

dtudury + 0 comments thank you!

L and R are inclusive (really, that was pretty clear... but for loops write themselves and prefer

`<`

to`<=`

)

uvijay + 0 comments waste of time

abhiranjan + 0 comments @ pr0grammer1, it seems you are able to solve this problem :) Let us know if you have any other query.

s4weng + 0 comments Me too, I don't understand this!

NoNo2 + 2 comments Question should be with strict time limit

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

Goodwine + 3 comments 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`

, and*mostSignificantBit*.benpfisher + 1 comment Is this considered constant time? I think so.

mcihanozer + 0 comments Could you give us more content about this solution?

Thanks!

dead_pool + 1 comment 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.

furskytl + 1 comment I think it can be O(logR) complexity.

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

Alphablackwolf + 2 comments I have it in constant O(1) time here:

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

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

#include <climits> int maxXor(int a, int b) { if(a^=b) return ~INT_MIN>>__builtin_clz(a)-1; return 0; }

akshay_megharaj + 2 comments 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

int maxXor(int a, int b) { int value = a ^ b, result = 1; while (value) { value = value >> 1; result = result << 1; } return result - 1; }

jeremy_roy + 0 comments 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.

int maxXor(int l, int r) { int a = l ^ r; int max = 0; while (a != 0) { max |= a; a = a >> 1; } return max; }

Hiba007 + 3 comments Just One Line

return max([i^j for i in range(l, r+1) for j in range(i, r+1)])

vasil_kolomiets + 0 comments [deleted]Tej_Pratap_Singh + 0 comments neat.

qayum_khan_usa + 0 comments Here's a slightly more efficient solution in

**Python3**. It uses a lazy-evaluation generator rather than first creating a long list for the maximum; it also avoids needless edge values. Of course, this is neither as efficient nor as clever as the*analytical formula*discussed earlier.def maximizingXor(l, r): return max( a^b for a in range(l,r) for b in range(l+1,r+1) )

Sort 326 Discussions, By:

Please Login in order to post a comment