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

// class TrieNode {
// public:
//     TrieNode* bits[2];
//     int number;
//     TrieNode(){
//         this->bits[0]=NULL;
//         this->bits[1]=NULL;
//     }
// };

// class Solution {
// private: 
//     TrieNode* node = new TrieNode();
// public:
//     void insert(int v){
//         long long num=v;
//         TrieNode* root = node;
//         long long x=(1<<31);
//         for(int i=0 ; i<32 ; i++){
//             TrieNode* newNode = new TrieNode();
//             if((num&x)==0){
//                 num=num<<1;
//                 if(root->bits[0]!=NULL) continue;
//                 root->bits[0]=newNode;
//             }
//             else{
//                 num=num<<1;
//                 if(root->bits[1]!=NULL) continue;
//                 root->bits[1]=newNode;
//             }
//             root=newNode;
//         }
//         root->number = v;
//     }
    
//     int findMaxXor(int v){
//         TrieNode* root = node;
//         long long num=v;
//         long long x=(1<<31);
//         // int xorResult = 0;
//         for (int i = 0; i < 32; i++) {
//             int bit = (num & x) ? 1 : 0;
//             if (root->bits[1 - bit] != NULL) {
//                 // xorResult = (xorResult << 1) | 1;
//                 root = root->bits[1 - bit];
//             } else {
//                 // xorResult = (xorResult << 1);
//                 root = root->bits[bit];
//             }
//             x >>= 1;
//         }
//         return root->number;
//     }
    
//     int findMaximumXOR(vector<int>& nums) {
//         for(int i=0 ; i<nums.size() ; i++){
//             insert(nums[i]);
//         }
//         int mx=0;
//         for(int i=0 ; i<nums.size() ; i++){
//             int num = findMaxXor(nums[i]);
//             mx=max(mx,(num*nums[i]));
//         }
//         return mx;
//     }
// };


class TrieNode {
public:
    TrieNode* bits[2];
    TrieNode() {
        this->bits[0] = NULL;
        this->bits[1] = NULL;
    }
};

class Solution {
private:
    TrieNode* node = new TrieNode();
public:
    void insert(int num) {
        TrieNode* root = node;
        unsigned int mask = 1 << 31;  // Use unsigned to avoid overflow
        for (int i = 0; i < 32; i++) {
            int bit = (num & mask) ? 1 : 0;
            if (root->bits[bit] == NULL) {
                root->bits[bit] = new TrieNode();
            }
            root = root->bits[bit];
            mask >>= 1;
        }
    }
    
    int findMaxXor(int num) {
        TrieNode* root = node;
        unsigned int mask = 1 << 31;  // Use unsigned to avoid overflow
        int xorResult = 0;
        for (int i = 0; i < 32; i++) {
            int bit = (num & mask) ? 1 : 0;
            if (root->bits[1 - bit] != NULL) {
                xorResult = (xorResult << 1) | 1;
                root = root->bits[1 - bit];
            } else {
                xorResult = (xorResult << 1);
                root = root->bits[bit];
            }
            mask >>= 1;
        }
        return xorResult;
    }
    
    int findMaximumXOR(vector<int>& nums) {
        for (int num : nums) {
            insert(num);
        }
        int mx = 0;
        for (int num : nums) {
            int xorValue = findMaxXor(num);
            mx = max(mx, xorValue);
        }
        return mx;
    }
};

175701