<p>Given an integer array <code>nums</code>, return <em>the maximum result of </em><code>nums[i] XOR nums[j]</code>, where <code>0 &lt;= i &lt;= j &lt; n</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,10,5,25,2,8]
<strong>Output:</strong> 28
<strong>Explanation:</strong> The maximum result is 5 XOR 25 = 28.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [14,70,53,83,49,91,36,80,92,51,66,70]
<strong>Output:</strong> 127
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

#define ff first
#define ss second
struct Node{
    Node* links[2]={NULL};
    bool flag=false;
    
    void put(int c, Node* nw){
        links[c]=nw;
        return;
    }
    
    Node* get(int c){
        return links[c];
    }
    
    bool isend(){
        return this->flag;
    }
    
    void setend(){
        this->flag=true;
        return;
    }
};
class Trie{
    public:
    Node* root;
    Trie(){
        root=new Node();
    }

    void insert(int n){
        int mask=1<<30,ct=0;
        Node* cur=root;
        while(mask){
            int f=((n&mask)>0);
            if(cur->get(f)==NULL)
            cur->put(f, new Node);
            cur=cur->get(f);
            mask/=2;
            ct++;
        }
        cur->setend();
    }

    int find_max(){
        Node* cur=root;
        int ans=0,mask=1<<30;
        //cout<<mask<<"   ";
        queue<pair<Node*,Node*>> q;
        while(mask){
            if(cur->get(0)&&cur->get(1))
            ans|=mask,q.push({cur->get(0),cur->get(1)});
            mask/=2;
            if(q.size())
            break;
            if(cur->get(0))
            cur=cur->get(0);
            else
            cur=cur->get(1);
        }

        //cout<<q.size()<<" "<<ans<<"    ";

        while(mask){
            int f=0;

            stack<pair<int,pair<Node*,Node*>>> s;
            while(q.size()){
                auto val=q.front();
                auto x=val.ff;
                auto y=val.ss;

                if(x->get(0)&&y->get(1))
                f=1,s.push({1, {x->get(0),y->get(1)}});

                if(x->get(1)&&y->get(0))
                f=1,s.push({1, {x->get(1),y->get(0)}});

                if(f==0&&x->get(0)&&y->get(0))
                s.push({0, {x->get(0),y->get(0)}});

                if(f==0&&x->get(1)&&y->get(1))
                s.push({0, {x->get(1),y->get(1)}});

                q.pop();
            }

            while(s.size()){
                auto val=s.top();
                s.pop();
                if(val.ff==f)
                q.push(val.ss);
            }
            ans|=(f*mask);
            mask/=2;
        }


        return ans;
    }
};

class Solution {
public:
    int findMaximumXOR(vector<int>& a) {
        Trie tr;
        for(auto i: a)
        tr.insert(i);

        return tr.find_max();
    }
};
255021