Maximum XOR of Two Numbers in an Array -- LeetCode

[Question]

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

[Analysis]
The brute force approach is to XOR each two of those numbers and find the maximum result. The time complexity is O(N^2).

Consider the maximum result's MSB (Most Significant Bit), there are two numbers from input set that can generate (XOR) the '1' in the position. That means in the position of that bit, (1) there are at least two numbers differ from each other; (2) For the bits to the left of that bit, no two numbers differ from each other. Then consider Most Significant Two Bits, Three Bits, ... , the same logic can apply. Therefore, each bit in maximum result can be decided.

[Solution]
class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        if (nums.size()<2) return 0;
     
        long mask = 0;
        long max = 0;
        for (int i=31; i>=0; i--) {
            unordered_set<long> pre_set;
            mask = mask | (1<<i);
            for (auto& n: nums) {
                pre_set.insert( n & mask );
            }
            // -- optional
            if (pre_set.size()==1) continue;
         
            long target = max | (1<<i);
            for (auto& x: pre_set) {
                   // -- if target^x=y then x^y=target
                if ( pre_set.count(x ^ target)> 0 ) {
                    max = target;
                    break;
                }
            }
        }
        return max;
    }

};