LC 0421 [M] Maximum XOR of Two Numbers in an Array - ALawliet/algorithms GitHub Wiki
https://www.youtube.com/watch?v=r8BAp3lFZ48&ab_channel=%E5%B1%B1%E6%99%AF%E5%9F%8E%E4%B8%80%E5%A7%90
# find the two numbers with the most opposite bits to the left side such that the result is the max 1s to the left side
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
mask = 0
maxres = 0
for i in range(32,-1,-1): # we know the max is 32 1s (2^32)
mask = mask | (1 << i) # 1000000 to keep/change/remove a desired part of the information, OR | is just adding them like +=
found = set() # we try to find the max 1s possible by generating the set of all possible prefix
for num in nums:
found.add(mask & num) # we want to light up the 1s from the left in the mask with the current number
# the & is lit up is the num is 1 for the max from the left so far in the mask
# now the found set is essentially the complements like in 2SUM
# so we can scan from left to right and try to fill in as many 1s
tmp = maxres | (1 << i) # same as mask but we need a tmp so we don't alter it
for prefix in found:
XOR = tmp^prefix # this is 2SUM complement: a^b=c, a^c=b
if XOR in found:
maxres = tmp # if we could not find the prefix in the hashset, then we do not get a bigger max result
return maxres
#O(32n) -> O(n)
'''
5 -> 00101
25 -> 11001
=
28 -> 11100 (16 + 8 + 4)
'''