<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 TrieNode {
    bool exists;
    TrieNode *nodes[2];

    TrieNode() {
        exists = false;
        nodes[1] = nodes[0] = nullptr;
    }
};

void insert(TrieNode *root, int num) {
    vector<int> bits(32, 0);
    
    for (int i = 0; i < 32; i++) {
        int m = 1<<i;
        if (num & m)
            bits[i] = 1;
    }
    
    TrieNode *curr = root;
    for (int i = 31; i >= 0; i--) {
        int b = bits[i];
        if (!curr->nodes[b])
            curr->nodes[b] = new TrieNode();
        curr = curr->nodes[b];
    };

    curr->exists = true;
}

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        TrieNode *root = new TrieNode();

        for (int el: nums)
            insert(root, el);

        int ans = 0;
        for (int el: nums) {
            // max xor
            TrieNode *curr = root;
            int comp = 0;
            for (int b = 31; b >= 0; b--) {
                int m = 1<<b;
                int d = 1;
                if (el & m)
                    d = 0;
                if (curr->nodes[d]) {
                    curr = curr->nodes[d];
                    comp += d * m;
                } else if (curr->nodes[1 - d]) {
                    comp += (1 - d) * m;
                    curr = curr->nodes[1 - d];
                } else
                    break;
            }
            // cout<<el<<" "<<comp<<"\n";
            ans = max(ans, comp ^ el);
        }

        return ans;
    }
};
349213