Question
Given 2 integers l and r, find the maximal value of a xor b, where a and b satisfy the following condition:
l ≤ a ≤ b ≤ r
For example, if l = 11
and r = 12
, then
11⊕11 = 0
11⊕12 = 7
12⊕12 = 0
Our maximum value is 7.
Naive Solution
A naive solution is to calculate XOR value for all values in the range and find the maximum.
def maximizingXOR(l, r):
# Since xor of equal values is 0
if l == r:
return 0
# Set an initial max value
_max = -1
# Iterate over all values in the range
for i in range(l, r+1):
for j in range(l, r+1):
# Replace the max value if the xor is greater than the current max value
_max = max(i ^ j, _max)
# Return the max value
return _max
Time Complexity
O(N2) where N is the range i.e. N = r - l + 1.
Efficient Solution
Lets look at the XOR operation first. For binary values, XOR is:
0⊕0 = 0
1⊕1 = 0
0⊕1 = 1
1⊕0 = 0
So, XOR is 0 for same bits and 1 for different bits.
Now, lets consider the pattern of binary values from l to r. Since l is smaller than r, so the first bit from l to r either changes from 0 to 1 or it remains 1.
Example 1:
l = 10 = (01010)2
r = 20 = (10100)2
Here the first bit changes from 0 to 1.
Example 2:
l = 10 = (1010)2
r = 15 = (1111)2
Here the first bit remains 1.
So if we take XOR of any 2 numbers in the range [l, r]
, for maximum value their first bit will be fixed which will be the same as the first bit of XOR of l and r itself.
Now lets observe the XOR of l and r. From its most significant bit, we know that the maximum XOR value in the range will have the same most significant bit. Its most significant bit also tells us the maximum value we can achieve i.e. let XOR of l and r be 1xxx where x can be 0 or 1 then maximum XOR value we can get is 1111 because from l to r its possible to choose 2 numbers in such a way that all x in xxx become 1.
Example 1:
l = 10 = (01010)2
r = 20 = (10100)2
l ^ r = (01010) ^ (10100) = (11110)
Now as l ^ r is of the form (1xxxx), we get the maximum XOR as (11111) by choosing a and b as 15 and 16 (01111 and 10000).
Example 2:
l = 10 = (1010)2
r = 15 = (1111)2
l ^ r = (1010) ^ (1111) = (0101)
Now as l ^ r is of the form (1xx), we get the maximum XOR as (111) by choosing a and b as 10 and 13 (1010 and 1101).
So to get the maximum XOR value, we just need (l ^ r)
. Calculate (l ^ r)
first and then from most significant bit of this value, we will add all 1s to get the final result.
Efficient Solution 1
def maximizingXOR(l, r):
result = 1
xor = l ^ r # 1xxx
# iterate for (MSB+1) times
while xor:
result <<= 1
xor >>= 1
# return MSB with all added 1s i.e. if xor was 1xxx return 1111
return result - 1
Time Complexity
O(logN) where N is the range i.e. N = r - l + 1.
Efficient Solution 2
Another solution is to directly use the log function to get the most significant bit.
import math
def maximizingXOR(l, r):
# log(0) is not possible, so condition to prevent it
if l == r:
return 0
return (1 << (int(math.log(l ^ r, 2)) + 1)) - 1
Time Complexity
O(1) assuming log function takes O(1) time.
Top comments (0)