<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 Solution {
 public:
  int findMaximumXOR(vector<int>& nums) {
    const int maxNum = ranges::max(nums);
    if (maxNum == 0)
      return 0;
    const int maxBit = static_cast<int>(log2(maxNum));
    int ans = 0;
    int prefixMask = 0;  // Grows like: 10000 -> 11000 -> ... -> 11111.

    // If ans is 11100 when i = 2, it means that before we reach the last two
    // bits, 11100 is the maximum XOR we have, and we're going to explore if we
    // can get another two 1s and put them into `ans`.
    for (int i = maxBit; i >= 0; --i) {
      prefixMask |= 1 << i;
      unordered_set<int> prefixes;
      // We only care about the left parts,
      // If i = 2, nums = {1110, 1011, 0111}
      //    -> prefixes = {1100, 1000, 0100}
      for (const int num : nums)
        prefixes.insert(num & prefixMask);
      // If i = 1 and before this iteration, the ans is 10100, it means that we
      // want to grow the ans to 10100 | 1 << 1 = 10110 and we're looking for
      // XOR of two prefixes = candidate.
      const int candidate = ans | 1 << i;
      for (const int prefix : prefixes)
        if (prefixes.contains(prefix ^ candidate)) {
          ans = candidate;
          break;
        }
    }

    return ans;
  }
};
314511