# 0421. Maximum XOR of Two Numbers in an Array
###### tags: `Leetcode` `Medium` `Bit Manipulation` `Trie`
Link: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
## 思路 $O(N)$ $O(1)$
space complexity是O(1)，是因为trie的大小是固定的
首先把每个数转成二进制存进trie里面，越高位越靠近root
然后对于每一个数字，从root开始找，用currsum记录当前路径得到的xor值，有没有在当前位(从右往左第$i$位)跟他数字不一样的数
## Code

class TrieNode{
    TrieNode[] children = new TrieNode[2];
}
class Solution {
    public int findMaximumXOR(int[] nums) {
        TrieNode root = new TrieNode();
        for(int num:nums){
            TrieNode curr = root;
            for(int i = 31;i >= 0;i--){
                int curBit = (num >> i) & 1;
                if(curr.children[curBit] == null){
                    curr.children[curBit] = new TrieNode();
                }
                curr = curr.children[curBit];
            }
        }
        
        int ans = Integer.MIN_VALUE;
        for(int num:nums){
            int curSum = 0;
            TrieNode curr = root;
            for(int i = 31;i >= 0;i--){
                int curBit = (num >> i) & 1;
                if(curr.children[curBit^1]!=null){
                    curr = curr.children[curBit^1];
                    curSum += (1<<i);
                }
                else{
                    curr = curr.children[curBit];
                }
            }
            ans = Math.max(ans, curSum);
        }
        return ans;
    }
}