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.
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 ^.
Let , it is easy to see that (since , have at most n bits, so the bitwise xor can not be larger than ).
Now assume that and . This is equivalent to that the binary expansion of and differs by the most significant bit, i.e.,
and .
Then
and satisfies and which achieves the upper bound of the xor of two numbers less than . Thus the maximum of for is , where n is the bit length of .
Whatever number is calculated in this way may not be in actual domain of possible values. How can correctness of this solution can be proved and verified.
Hi. I cannot provide a formal mathematical proof, mostly because it would probably take 4 paragraphs of explaining in detail. It's best to just see it always works by going through a few examples on your own.
A good thing to notice is that the number calculated will always be in the actual domain of possible values because my solution says "We first find the most significant bit that we can force to differ by looking at L and R." This is the main step that gets A and B to be in the correct domain.
Designate the bits of a number x in the range as b_i, where b_0 is the least significant bit and b_31 (assuming a 32-bit integer) is the most significant bit. Let b_n be the most significant bit that changes over the range from l to r. Note that if b_n changed from 1 to 0 as we increment x, that would result in a carry to b_n+1, which contradicts b_n being the most significant bit to change. Ergo b_n must be 0 at l, switch to 1 at some point, never switch back, and be 1 at r, and b_n must differ (and be the largest bit that differs) between l and r.
Given that, there must be some x_0 which is the largest number between l and r where b_n is 0, and some x_1 which is the smallest number between l and r where b_n is 1, and x_0 + 1 = x_1. In order to b_n to change when adding 1 to x_0, it must receive a carry from b_n-1, which must in turn receive a carry from b_n-2, and so on down to b_0. Thus in x_0 all the bits from b_0 to b_n-1 must be 1. Correspondingly, after adding 1 all those bits will flip as the carry propagates, so in x_1 all the bits from b_0 to b_n-1 will be 0.
Therefore, we take x_0 ^ x_1. As proven above, all the bits from b_0 to b_n differ between x_0 and x_1, and of course the bits from b_n+1 up do not differ since by assumption they are constant for all x between l and r. Thus we can get a result where all bits up to b_n are 1 in the xor, and as every higher bit must be 0 for any pair of numbers between l and r since those bits never vary this must be maximal.
Your version of the code works also. I used 31 instead of 32 since I count the 32 bits from 0 to 31 instead of 1 to 32. That is, I count the leftmost bit as the 31st bit, and the rightmost bit as the 0th bit.
@rshaghoulian
Instead of substracting from 31 can we substract from 32 and do not add 1 later? or there is something I am missing because of it, it is required to substract from 31?
Yes, you can do that. I subtract from 31 since I like to number the bits 0 to 31 (from right to left). If you subtract from 32, it's kind of like numbering the bits 1 to 32.
L ^ r - gets you the maximum XOR value between l and r.
format( a_number, 'b') - returns the binary string of a_number
wrapping that in a len() gets you the length of that binary string which is what you want the length of all 1s to be.
<< - is a bitshift operator, for example x << y shifts the binary of x to the left y times. ie. 2('10') << 1 = 4('100'). 4('100') << 1 = 8('1000')
put it all together and you have 1 left-bitshifted by the length of the number that l^r gives minus 1.
you subtract by 1 for two reasons:
A) when you shift 1 by that number, you have one extra bit in your bitstring
for example, if you 1<<3 you get 8, which is 1000, but the len() is 3, so you want 3 bits of all 1s which brings us to B)
B)when you subtract 8(1000) by 1 you get 7(111) which is the len() of all 1s
Maximizing XOR
You are viewing a single comment's thread. Return to all comments →
Java solution - more efficient than Editorial solution
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
Notice how we don't directly calculate the values of A and B.
From my HackerRank solutions.
pro!
Nice solution :)
Here is a one liner in C++
can you explane it
https://srikantpadala.com/blog/hackerrank-solutions/maximizing-xor U can refer the above link .
Link not working
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?
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 ^.
thank you
It is a nice solution. My solution is similar with no additional method calls.
How did you arrive to the solution? plz explain...
Guess we can prove it like this.
Let , it is easy to see that (since , have at most n bits, so the bitwise xor can not be larger than ).
Now assume that and . This is equivalent to that the binary expansion of and differs by the most significant bit, i.e., and .
Then and satisfies and which achieves the upper bound of the xor of two numbers less than . Thus the maximum of for is , where n is the bit length of .
ipynotebook here
The proof goes like 1. estimate a upper bound of and 2. find and that satisfies the constraint and achieves the upper bound.
Let's say (binary) and , then we can construct:
(put 1 at the most significant bit followed by 0s) and
(put 0 at the most significant bit followed by 1s)
so that . And the constraints are also satisfied.
Hope this example helps.
Thxxx!! :)))
explain plz..
nice code!!! beautiful logic
Thanks for the solution, loved it!!
Thank You @rshaghoulian.
Great one ¡¡¡¡!!!!!
Whatever number is calculated in this way may not be in actual domain of possible values. How can correctness of this solution can be proved and verified.
Hi. I cannot provide a formal mathematical proof, mostly because it would probably take 4 paragraphs of explaining in detail. It's best to just see it always works by going through a few examples on your own.
A good thing to notice is that the number calculated will always be in the actual domain of possible values because my solution says "We first find the most significant bit that we can force to differ by looking at L and R." This is the main step that gets A and B to be in the correct domain.
HackerRank solutions.
Thanks for explaining. A very few explain code well. Keep it up.
I can provide a proof.
Designate the bits of a number x in the range as b_i, where b_0 is the least significant bit and b_31 (assuming a 32-bit integer) is the most significant bit. Let b_n be the most significant bit that changes over the range from l to r. Note that if b_n changed from 1 to 0 as we increment x, that would result in a carry to b_n+1, which contradicts b_n being the most significant bit to change. Ergo b_n must be 0 at l, switch to 1 at some point, never switch back, and be 1 at r, and b_n must differ (and be the largest bit that differs) between l and r.
Given that, there must be some x_0 which is the largest number between l and r where b_n is 0, and some x_1 which is the smallest number between l and r where b_n is 1, and x_0 + 1 = x_1. In order to b_n to change when adding 1 to x_0, it must receive a carry from b_n-1, which must in turn receive a carry from b_n-2, and so on down to b_0. Thus in x_0 all the bits from b_0 to b_n-1 must be 1. Correspondingly, after adding 1 all those bits will flip as the carry propagates, so in x_1 all the bits from b_0 to b_n-1 will be 0.
Therefore, we take x_0 ^ x_1. As proven above, all the bits from b_0 to b_n differ between x_0 and x_1, and of course the bits from b_n+1 up do not differ since by assumption they are constant for all x between l and r. Thus we can get a result where all bits up to b_n are 1 in the xor, and as every higher bit must be 0 for any pair of numbers between l and r since those bits never vary this must be maximal.
I have a question, why did you have
Instead of 32, which represents the 32bits used for an int.
Using the base example of L = 10, R = 15
L ^ R = 1010 ^ 1111 = 0101 = 5
The result of Integer.numberOfLeadingZeros(xored) is 29, which matches 32bits - 3bits (for 5)
And then your result would be
Just trying to learn on your reasoning to use 31.
Your version of the code works also. I used 31 instead of 32 since I count the 32 bits from 0 to 31 instead of 1 to 32. That is, I count the leftmost bit as the 31st bit, and the rightmost bit as the 0th bit.
HackerRank solutions.
Nice solution. It can be written in one line:
I didn't get this. Somenone plz explain this thing.
@rshaghoulian Instead of substracting from 31 can we substract from 32 and do not add 1 later? or there is something I am missing because of it, it is required to substract from 31?
Yes, you can do that. I subtract from 31 since I like to number the bits 0 to 31 (from right to left). If you subtract from 32, it's kind of like numbering the bits 1 to 32.
HackerRank solutions.
Thanks.
We can also do -
The logic is same. One additional charactersitics that's been used is:- Sum of all the trailing zeros converted to ones is HighestBit - 1.
For eg - L = 10111
R = 11100 _X___ <-- that's most significant differing bit 01000 <-- This is what HighestBit gave us.
We need to calculate 01111 in int, this can be obtained by sum of 01000 and 00111 and that's equal to 2*highestBit - 1.
This is absolutely great! Here, this is same operation in PHP,
In the spirit of this solution, here's one in Python:
Cool! How did you come up with this solution?
L ^ r - gets you the maximum XOR value between l and r.
format( a_number, 'b') - returns the binary string of a_number
wrapping that in a len() gets you the length of that binary string which is what you want the length of all 1s to be.
<< - is a bitshift operator, for example x << y shifts the binary of x to the left y times. ie. 2('10') << 1 = 4('100'). 4('100') << 1 = 8('1000')
put it all together and you have 1 left-bitshifted by the length of the number that l^r gives minus 1.
you subtract by 1 for two reasons: A) when you shift 1 by that number, you have one extra bit in your bitstring for example, if you 1<<3 you get 8, which is 1000, but the len() is 3, so you want 3 bits of all 1s which brings us to B) B)when you subtract 8(1000) by 1 you get 7(111) which is the len() of all 1s
hopefully that makes sense.
Awesome
genius!!
good observation !
Awe!!!!
Python Oneliner Solution
bro can you explain your code
if a=8 and b=31,your answer will be 31 but for answer to be 31 we should xor 31 with zero which is not in the given range.
11111 in binary is 31 in decimal. We can create that by XORING: 16 with 15
HackerRank solutions.
Can anyone explain what is significant bit.I am a self taught programmer
In a given binary value the left most bit is a msb(most significant bit) and the right most bit is lsb(least significant bit).
For eg : 1000 0000 (Hex - 0x80) Left most bit '1' is msb and the right most bit '0' is lsb
PYTHON SOLUTION. NOT A ONE LINER. BUT EASY TO UNDERSTAND FOR BEGINEERS LIKE ME ;) def maxXor( l, r):
max_xor = 0
for low in range(l ,r+1):
return max_xor
it is straight forward logic but i have a doubt whether it will pass all the test
it passed all the test . it is the code that i have used .
Give this man a medal!