> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/lian-xi/maximum-xor-of-two-numbers-in-an-array.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.