LeetCode 421. Maximum XOR of Two Numbers in an Array

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int ans = 0;
        for (int i = 30; i >= 0; --i) {
            unordered_set<int> seen;
            for (auto num : nums)
                seen.insert(num >> i);
            int next = (ans << 1) + 1;
            bool found = false;
            for (auto num : nums)
                if (seen.find(next ^ (num >> i)) != seen.end()) {
                    found = true;
                    break;
                }
            ans = found ? next : next - 1;
        }
        return ans;
    }
};