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