<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(): m_children(vector<TrieNode*>(2, nullptr)){}
//     // std::array<unique_ptr<TrieNode>, 2> m_children;
//     vector<TrieNode*> m_children;
// };

class Solution {
public:
//     int findMaximumXOR(vector<int>& nums) {
//         int maxElem = *max_element(nums.begin(), nums.end());

//         if (maxElem == 0)
//             return 0;

//         m_maxBits = std::floor(std::log2(maxElem)) + 1;

//         int maxXor = 0;

//         for (int num: nums)
//             maxXor = std::max(maxXor, insert(num));

//         return maxXor;
//     }

// private:
//     int insert(int num) {
//         auto* node = m_root.get();
//         auto* xorNode = m_root.get();
//         int currXor = 0;

//         for (int i = m_maxBits - 1; i >= 0; --i) {
//             int bit = 1 & num >> i;
//             int toggledBit = bit ^ 1;

//             if (!node->m_children[bit])
//                 node->m_children[bit] = new TrieNode();
//             node = node->m_children[bit];

//             if (xorNode->m_children[toggledBit]) {
//                 xorNode = xorNode->m_children[toggledBit];
//                 currXor |= 1 << i;
//             } else {
//                 xorNode = xorNode->m_children[bit];
//             }
//         }

//         return currXor;
//     }

//     unique_ptr<TrieNode> m_root = make_unique<TrieNode>();
//     int m_maxBits = 0;




    int findMaximumXOR(vector<int>& nums) {
        int maxElem = *max_element(nums.begin(), nums.end());

        if (maxElem == 0)
            return 0;

        int bits = floor(log2(maxElem)) + 1;

        int n = nums.size(), maxXOR = 0, curr;

        unordered_set<int> prefixes;

        for (int bit = bits - 1; bit >= 0; --bit) {
            maxXOR <<= 1;
            curr = maxXOR | 1;

            prefixes.clear();

            for (int num: nums)
                prefixes.insert(num >> bit);

            for (int num: prefixes) {
                if (prefixes.count(curr ^ num)) {
                    maxXOR = curr;
                    break;
                }
            }
        }

        return maxXOR;
    }
};

auto init = []() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
} ();
205446