XOR

class TrieNode{
    public:
    unordered_map<int, TrieNode*> children;
    TrieNode(){
        children = unordered_map<int, TrieNode*>();
    }
};

class Trie{
  public:
    TrieNode* root;

    Trie(){
        root = new TrieNode();
    }

    void insert(int x){
        TrieNode* cur = root;
        for(int j=30;j>=0;j--){
            int v =  ((x)&(1<<j)!=0);
            if(cur->children.find(v)==cur->children.end()){
                cur->children[v] = new TrieNode();
            }
            cur = cur->children[v];
        }
    }

    int maxXOR(int x){
        TrieNode* cur = root;
        int ans = 0;
        for(int j = 30; j >= 0; j--){
            if((x & (1<<j))!=0){
                if(cur->children.find(0)!=cur->children.end())
                {
                    ans += (1<<j);
                    cur = cur->children[0];
                    // cout<<"0A";
                }
                else
                {
                    // ans += (1<<j);
                    cur = cur->children[1];
                    // cout<<"1A";
                }
            }
            else
            {
                if(cur->children.find(1)!=cur->children.end())
                {
                    ans += (1<<j);
                    cur = cur->children[1];
                    // cout<<"1B";
                }
                else
                {
                    // ans += (1<<j);
                    cur = cur->children[0];
                    // cout<<"0B";
                }
            }
        }
        // cout<<"\n";
        return ans;
    }
};

class Solution {

public:
    int findMaximumXOR(vector<int>& nums){
        int ans = 0;
        Trie trie;
        for(auto x : nums){
            trie.insert(x);
            ans = max(ans, trie.maxXOR(x));
            // cout << x << " " << ans <<"\n";
        }
        return ans;
    }
};