Maximum Xor of Two Numbers in an Array
Created: March 30, 2020 by [lek-tin]
Last updated: March 30, 2020
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example
Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.
Solution (prefix hashset - less efficient)
Time: O(N)
Space: O(1)
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
# 0bxxxxxx - 0b
L = len(bin(max(nums))) - 2
max_xor = 0
for i in range(L-1, -1, -1):
max_xor <<= 1
print("max_xor:", bin(max_xor) )
# set the rightmost bit to 1
curr_xor = max_xor | 1
print("curr_xor:", bin(curr_xor) )
# highest (L-i) bits
prefixes = {num >> i for num in nums}
print("prefixes:", [bin(p) for p in prefixes] )
# as long as there exists a p that makes curr_xor^p > 0
# Update max_xor, if two of these prefixes could result in curr_xor.
# Check if p1^p2 == curr_xor, i.e. p1 == curr_xor^p2
# because if a^b = c => b^c = a / a^c = b
max_xor |= any(curr_xor^p in prefixes for p in prefixes)
print("max_xor:", bin(max_xor) )
print("--------")
return max_xor
# input: [3,10,5,25,2,8]
# max_xor: 0b0
# curr_xor: 0b1
# prefixes: ['0b0', '0b1']
# max_xor: 0b1
# --------
# max_xor: 0b10
# curr_xor: 0b11
# prefixes: ['0b0', '0b1', '0b11']
# max_xor: 0b11
# --------
# max_xor: 0b110
# curr_xor: 0b111
# prefixes: ['0b0', '0b1', '0b10', '0b110']
# max_xor: 0b111
# --------
# max_xor: 0b1110
# curr_xor: 0b1111
# prefixes: ['0b1', '0b10', '0b100', '0b101', '0b1100']
# max_xor: 0b1110
# --------
# max_xor: 0b11100
# curr_xor: 0b11101
# prefixes: ['0b10', '0b11', '0b101', '0b1000', '0b1010', '0b11001']
# max_xor: 0b11100
# --------
Solution (prefix trie - more efficient)
Time: O(N)
Space: O(1)