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

// 93 ms 37.4 MB add GCC and IO
// sample 91 ms submission
#pragma GCC optimize("Ofast")
#pragma GCC taget("avx,avx2,fma")
static const int _ = [] { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0; }();
class Solution
{
public:
    int dfs(vector<int> &nums, int l1, int r1, int l2, int r2, int k)
    {
        if(l1 == r1 && l2 == r2)
        {
            return nums[l1] ^ nums[l2];
        }

        if(k == -1)
        {
            return 0;
        }

        int pos1 = lower_bound(nums.begin() + l1, nums.begin() + r1 + 1, 1 << k) - nums.begin();
        int pos2 = lower_bound(nums.begin() + l2, nums.begin() + r2 + 1, 1 << k) - nums.begin();

        for(int i = pos1; i <= r1; ++i)
        {
            nums[i] -= 1 << k;
        }

        for(int i = pos2; i <= r2; ++i)
        {
            nums[i] -= 1 << k;
        }

        int val1 = 0,
            val2 = 0;

        if(pos1 > l1 && pos2 <= r2)
        {
            val1 = dfs(nums, l1, pos1 - 1, pos2, r2, k - 1) + (1 << k);
        }

        if(pos1 <= r1 && pos2 > l2)
        {
            val2 = dfs(nums, pos1, r1, l2, pos2 - 1, k - 1) + (1 << k);
        }

        if(val1 || val2)
        {
            return max(val1, val2);
        }

        return dfs(nums, l1, r1, l2, r2, k - 1);
    }

    int findMaximumXOR(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());

        if(nums.size() == 1)
        {
            return 0;
        }

        int n = nums.size();
        int k = 30,
            pos = 0;

        while(k >= 0)
        {
            int u = 1 << k;

            pos = lower_bound(nums.begin(), nums.end(), u) - nums.begin();

            if(pos == 0)
            {
                for(int i = 0; i < nums.size(); ++i)
                {
                    nums[i] -= u;
                }
            }

            if(pos != 0 && pos != n)
            {
                for(int i = pos; i < n; ++i)
                {
                    nums[i] -= u;
                }

                break;
            }

            k--;
        }

        return dfs(nums, 0, pos - 1, pos, n - 1, k - 1) + (1 << k);
    }
};
61678