# Leetcode 421 Maximum Xor of Two Numbers in an Array

// Author: Huahua
class Trie {
public:
Trie(): children(2) {}
vector<unique_ptr<Trie>> children;
};
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
Trie root;

// Insert a number into the trie.
auto insert = [&](Trie* node, int num) {
for (int i = 31; i >= 0; --i) {
int bit = (num >> i) & 1;
if (!node->children[bit])
node->children[bit] = std::make_unique<Trie>();
node = node->children[bit].get();
}
};

// Find max xor sum of num and another element in the array.
auto query = [&](Trie* node, int num) {
int sum = 0;
for (int i = 31; i >= 0; --i) {
int bit = (num >> i) & 1;
if (node->children[1 - bit]) {
sum += (1 << i);
node = node->children[1 - bit].get();
} else {
node = node->children[bit].get();
}
}
return sum;
};

// Insert all numbers.
for (int x : nums)
insert(&root, x);

int ans = 0;
// For each number find the maximum xor sum.
for (int x : nums)
ans = max(ans, query(&root, x));
return ans;
}
};

static int x = [] () {ios::sync_with_stdio(false); cin.tie(0); return 0;} ();
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
int res = 0, mask = 0;
for (int i=31; i>=0; --i) {
unordered_set<int> s;
for (const int num: nums)
int t = res | (1 << i);
for (const int prefix: s)
if (s.count(t ^ prefix)) {
res = t;
break;
}
}
return res;
}
};


class Solution_TLE {
public:
int findMaximumXOR(vector<int>& nums) {
int res = 0;
for (int i = 0, n = nums.size(); i < n; ++i)
for (int j = i + 1; j < n; ++j)
res = max(res, nums[i] ^ nums[j]);
return res;
}
};


###### #直达链接

LeetCode 421. Maximum XOR of Two Numbers in an Array