# 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`.

&#x20;

**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
```

&#x20;

**Constraints:**

* `1 <= nums.length <= 2 * 105`
* `0 <= nums[i] <= 231 - 1`

```python
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
```