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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Bit manipulation

Data structures

Starter code: class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        

Solutions:
class Solution:

	def findMaximumXOR(self, nums):
		ans = 0
		for bit in range(31, -1, -1):
			ans = (ans << 1) + 1
			pre = set()
			for n in nums:
				p = n >> bit & ans
				if p in pre:
					break
				pre.add(ans - p)
			else:
				ans -= 1
		return ans