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

#pragma GCC optmize ("03","unroll-loops")
struct node
{
    node * links[2];
    bool containskey(int x)
    {
        return links[x]!=nullptr;
    }
    void put(int x)
    {
        links[x] = new node();
    }
    node * get(int x)
    {
        return links[x];
    }
};
class Trie
{
    node *root;
    public:
    Trie()
    {
        root = new node();
    }
    void insert(int x)
    {
        node * temp = root;
        int bit;
        for(int i=31;i>=0;i--)
        {
            bit = (x>>i) & 1;
            if(!temp->containskey(bit))
                temp->put(bit);
            temp = temp->get(bit);
        }
    }
    int f(int x)
    {
        node * temp = root;
        
        int max_xor = 0;
        int bit;
        for(int i=31;i>=0;i--)
        {
            bit = x>>i & 1;
            if(temp->containskey(1-bit))
            {
                max_xor = max_xor | (1<<i);
                temp = temp->get(1-bit);
            }
            /*else
                max_xor = max_xor>>i | (bit);*/
            else temp = temp->get(bit);
        }
        return max_xor;
    }
};
class Solution {
public:
    /*int findMaximumXOR(vector<int>& nums) 
    {
        int maxi = -1e9;
        int n = nums.size();
        for(int i=0;i<n;i++)
        {
            for(int j = i;j<n;j++)
            {
                maxi = max(maxi,(nums[i]^nums[j]));
            }
        }
        return maxi;    
    }*/
    int findMaximumXOR(vector<int>& nums)
    {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        Trie trie;
        //int maxi = -1e9;
        int n = nums.size();
        for(int i=0;i<n;i++)
            trie.insert(nums[i]);
        int maxi = 0;
        for(int i=0;i<n-1;i++)
        {
            maxi = max(maxi,trie.f(nums[i]));
        }
        return maxi;
    }
    
};

160828