Last Updated: 17 Nov, 2021
Maximize xor
Easy
Asked in companies
You have an integer array ‘A’ of the form of [x, x+1, x+2, x+3, …….]. As the array is vast in size, you are given both endpoints of the array, i.e., If you are given two integers, ‘L’ and ‘R’, the array ‘A’ will be [L, L+1, L+2, ……., R-1, R]. Your task is to find the maximum possible value of ‘X’ such that the following two conditions hold.
a ⊕ b = X, where ⊕ denotes bitwise xor operation.
Both numbers ‘a’ and ‘b’ belong to the array ‘A’.
Input Format:
The first line contains 'T', denoting the number of tests.
For each Test :
The only line contains two space-separated integers 'L' and 'R', denoting the endpoints of the array.
Output Format:
For each test, print an integer, denoting the maximum possible xor of two elements from the array.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints -
1 <= 'T' <= 10^3
1 <= 'L' <= 'R' <= 10^9
Time Limit: 1 sec
Approaches
Approach: Run two loops (nested) to find all possible pairs (a, b) such that (L <= a, b <= R) and calculate (a ⊕ b). Finally, return maximum xor value among all generated pairs.
Algorithm:
- Initialize answer with 0, i.e., ans = 0.
- Iterate a for loop, i = L to R.
- Iterate another for loop, j = i+1 to R.
- Find xor value for current pair.
- Maximize ‘ans’ with current xor value.
- Iterate another for loop, j = i+1 to R.
- Return ‘ans’.
Approach: An observation is that if we move from a smaller number to a larger one, their MSB in binary representation changes from 0 to 1 or remains unchanged.
In our pair (a, b), both numbers should be in the range [L, R], then the position of MSB (from right to left in binary) in a⊕b can never be greater than in L⊕R.
Let’s understand by an example.
Let L = 16 and R = 20.
L ⊕ R = (10000) ⊕ (10100) = (00100). Here, MSB is in 3rd position from the right side, which ensures that MSB can’t exceed the 3rd position for any pair (a, b) in the range [L, R]. Currently, our answer is 1xxxxx, where we know the position of bit ‘1’.
Now, the question arises, what to do with the remaining positions/bits?
To answer this question, our another observation is that, the position where we got MSB in L⊕R, one among L and R has bit ‘1’ at that place and another has bit ‘0’. So in the given range, at least once, the number is changed from ‘1111…..’ to ‘1000…..’ i.e., (2^p - 1) to (2^p). Hence it is always possible to choose combinations such that in 1xxxxx, each bit becomes ‘1’.
Algorithm:
- Calculate xor of L and R, let it be ‘L_xor_R’.
- Find the position of MSB in ‘L_xor_R’.
- Initialize ‘position’ with 0.
- While ‘L_xor_R’ is non-zero, divide it by two and increment the count of ‘position’.
- Construct a binary number having all bits 1s, and the count of bits is equal to ‘position’.
- The decimal representation of the above number is our desired answer.