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

struct trie{
    trie *one;
    trie *zero;

    trie()
    {
        one = NULL;
        zero = NULL;
    } 
};

trie *root;

string change(int i)
{
    string res(32,'0');
    int j =0;
    while(i)
    {
        if(i & 1)
        {
            res[j] = 1;
        }
        j++;
        i = i >> 1;
    }
    reverse(res.begin(),res.end());
    return res;
}
void insert(string str)
{
    trie* curr = root;
    for(auto i: str)
    {
        if(i == '0')
        {
            if(curr->zero == NULL)
            {
                curr->zero = new trie();
            }
            curr = curr->zero;
        }else{
            if(curr->one == NULL)
            {
                curr->one = new trie();
            }
            curr = curr->one;
        }
    }
}
 
 int find(string str)
 {
    trie *curr = root;
    int res = 0;
    int po = 31;
    for(auto i: str)
    {
        if(i == '0')
        {
            if(curr->one == NULL)
            {
                if(curr->zero == NULL)
                {
                    return res;
                }
                curr = curr->zero;
            }else{
                res += pow(2,po);
                curr = curr->one;
            }
        }else{
            if(curr->zero == NULL)
            {
                if(curr->one == NULL)
                {
                    return res;
                }
                curr = curr->one;
            }else{
                res += pow(2,po);
                curr = curr->zero;
            }
        }
        po--;
    }
    return res;
 }
class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        root = new trie();
        for(int i: nums)
        {
            string str = change(i);
            insert(str);
        }
        int res = 0;
        for(int i: nums)
        {
            string str = change(i);
            res = max(res,find(str));
        }
        return res;
    }
};
344256