# Maximum XOR of Two Numbers in an Array

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

分析

a^b=c => a^c =b. 所以用ans^a = b => a^b = ans    (a,b都是prevs)

每次这里只在乎每个Num的左半部分bit， ans >>=1 然后 ans^1（ 就是ans+1）让ans下一位变成1，如果能找到ans^a也在prevs里，这该数b^a = ans

```
class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32)[::-1]:
            prevs = [n>>i for n in nums]
            ans <<= 1
            ans += any(ans^1^p in prevs for p in prevs)
        return ans
```

Trie实现，只有2个子树0,1。每次尽量往相反方向走，0^1才能max

可行则 temp+=1<\<j. 或者直接最后叶子的值^当前Num

```
class TrieNode:
    def __init__(self):
        self.val = 0
        self.children = {}
       
class Solution:
    """
    @param nums: 
    @return: the maximum result of ai XOR aj, where 0 ≤ i, j < n
    """

    def findMaximumXOR(self, arr):
        root = TrieNode()
        
        for key in arr:
            node = root
            for i in range(31, -1, -1):
                curbit = key >> i & 1
                if curbit not in node.children:
                    node.children[curbit] = TrieNode()
                node = node.children[curbit]
            node.val = key
        
        
        res = 0
        for key in arr:
            node = root
            temp = 0
            for i in range(31, -1, -1):
                curbit = key >> i & 1
                
                if 1^curbit in node.children:
                    temp += 1 << i
                    node = node.children[1^curbit]
                elif curbit in node.children:
                    node = node.children[curbit]
            res = max(temp, res)
            
        return res
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/lian-xi/maximum-xor-of-two-numbers-in-an-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.