421. Maximum XOR of Two Numbers in an Array

Medium

---

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Constraints:

• 1 <= nums.length <= 2 * 105

• 0 <= nums[i] <= 231 - 1

class Trie():
    def __init__(self):
        self.one = None
        self.zero = None
        self.value = None
class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        root = Trie()
        for num in nums:
            node = root
            for i in range(32,-1,-1):
                mask = 1 << i # 00000100000000 1 at ith Position
                masked = num & mask
                if masked is 0:
                    if node.zero is None:
                        node.zero = Trie()
                    node = node.zero
                else:
                    if node.one is None:
                        node.one = Trie()
                    node = node.one
            node.value = num
        
        max_xor = 0
        for num in nums:
            node = root
            for i in range(32,-1,-1):
                mask = 1 << i
                masked  = num & mask
                if masked is 0:
                    if node.one:
                        node = node.one
                    else:
                        node = node.zero
                else:
                    if node.zero:
                        node = node.zero
                    else:
                        node = node.one
            max_for_num = num ^ node.value
            max_xor = max(max_xor, max_for_num)
        return max_xor