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.
----------------------------------------------------------------------------------------
Cycle bit by bit. For every bit, we could know the largest prefix expected. If the expected largest prefix could be xor by some two nums (implemented by hashSet), we could know the final answer. The complexity is O(n)
class Solution:
def findMaximumXOR(self, nums):
pre, mask = 0, 0
for i in range(31, -1, -1):
one = (1 << i)
mask |= one
exist = set()
cur_largest = pre | one
for num in nums:
cur = num & mask
if ((cur ^ cur_largest) in exist):
pre = cur_largest
else:
exist.add(cur)
return pre
s = Solution()
print(s.findMaximumXOR([3, 10, 5, 25, 2, 8]))