could you please re-explain the hint video .
Hint not clear for XOR profit
hello @gagangoyal674,
We need to maximise the xor between ‘small’ and ‘high’. So let’s take an example to understand this.
5 xor 2 = 101 xor 010 first case: MSB bit is not set for both the values in the range.If want to maximimize this then what we need to do is to keep the MSB of 5 (100) as it is and think about maximizing the remaining lower bits. As we know that lower bits all will be one for the case when everything is 11 which is nothing but 3 i.e. 2^2-1. Since the problem is talking about the range between 2 to 5 we defintely have 3 in the range. So all we need to do is to find out the highest MSB set in the larger of 2 values and add the remaining 1’s for the lower bits.
second case: As for the case when MSB is set for both the values in the range doing xor will defintely have those bits set as 0 and we need to go back to lower bits. Again for lower bits we need to repeat the same logic as first case. example: (10, 12) (1010, 1100) As you can see both have MSB set as 1 then we have to go back to lower bits which is 010 and 100. Now this problem is same as the first case.
There are several ways to code this. What I did is to do just the xor between ‘small’ and ‘high’ and that will remove MSB bit if both ‘small’ and ‘high’ have MSB bit set. Incase that is not the case then it will preserve the MSB bit. After that I am trying to make all lower bits 1’s by finding out the maximum power of 2 in the xored output and subtracting from 1.