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.
So I spent almost 2 hours to figure out this and this will definitely help you to save your time and clear your confusion.
Let's suppose we take l = 83 and r = 89.
83=1010011
89=1011001
Now we can divide binary strings of l and r into two parts based on the most significant different bit.
positions->6,5,43,2,1,083=101001189=1011001
Now position 3 is the leftmost position where the bits are different, anything to the left will not change because if we do so then it will either be less than l or becomes greater than r based upon the changes we make, since it is our constraint to remain inside the range l <= a,b <= r.
So the only changes we can make is in the second part of the binary strings.
Now watch this:
This is all possible permutations of a 4 bits long binary string.
In this pattern you can easily see that every line connects two different binary strings and they can be pairs a and b, smaller one being a and larger one being b.
So that a^b = 1111
Since our range is between 0011 to 1001 (from our original example of l = 83 and r = 89)
We can see that pairs 0111 ^ 1000 result in 1111
So we can say that if we make sure that, most significant bit of any two given binary strings are different i.e one is 0 and another one is 1 then we will always get atleast one pair between those range whose xor(^) will result in that bit long string with all the bits set to 1.
Conclusion you only need to find the position of leftmost different bit for l and r and after that it is not wrong to say that the maximum value of xor of any two numbers between that range will be equal to 111...(n+1) times where n is the position of the leftmost different bit.
In our case it is 1111 = 15.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Maximizing XOR
You are viewing a single comment's thread. Return to all comments →
So I spent almost 2 hours to figure out this and this will definitely help you to save your time and clear your confusion.
Let's suppose we take
l = 83
andr = 89
.Now we can divide binary strings of l and r into two parts based on the most significant different bit.
Now position 3 is the leftmost position where the bits are different, anything to the left will not change because if we do so then it will either be less than l or becomes greater than r based upon the changes we make, since it is our constraint to remain inside the range
l <= a,b <= r
.So the only changes we can make is in the second part of the binary strings.
Now watch this:
This is all possible permutations of a 4 bits long binary string.
In this pattern you can easily see that every line connects two different binary strings and they can be pairs a and b, smaller one being a and larger one being b.
So that
a^b = 1111
Since our range is between 0011 to 1001 (from our original example of l = 83 and r = 89)
We can see that pairs
0111 ^ 1000
result in1111
So we can say that if we make sure that, most significant bit of any two given binary strings are different i.e one is 0 and another one is 1 then we will always get atleast one pair between those range whose
xor(^)
will result in that bit long string with all the bits set to 1.Conclusion you only need to find the position of leftmost different bit for
l
andr
and after that it is not wrong to say that the maximum value of xor of any two numbers between that range will be equal to 111...(n+1) times where n is the position of the leftmost different bit.In our case it is
1111 = 15
.