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.
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.
Maximizing XOR
You are viewing a single comment's thread. Return to all comments →
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