Formatted question description: https://leetcode.ca/all/421.html
421. Maximum XOR of Two Numbers in an Array (Medium)
Given an integer array nums
, return the maximum result of nums[i] XOR nums[j]
, where 0 ≤ i ≤ j < n
.
Follow up: Could you do this in O(n)
runtime?
Example 1:
Input: nums = [3,10,5,25,2,8] Output: 28 Explanation: The maximum result is 5 XOR 25 = 28.
Example 2:
Input: nums = [0] Output: 0
Example 3:
Input: nums = [2,4] Output: 6
Example 4:
Input: nums = [8,10,2] Output: 10
Example 5:
Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70] Output: 127
Constraints:
1 <= nums.length <= 2 * 104
0 <= nums[i] <= 231 - 1
Related Topics:
Bit Manipulation, Trie
Solution 1. Trie
Flatten the bits information of the array into a Trie. For each number in array, use Trie to find the maximum value it can get using xor
.
// OJ: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
// Time: O(N)
// Space: O(1)
// Ref: https://discuss.leetcode.com/topic/63207/java-o-n-solution-using-trie
struct TrieNode {
TrieNode *next[2] = {};
};
class Solution {
void addNode(TrieNode *node, int n) {
for (int i = 31; i >= 0; --i) {
int bit = (n >> i) & 1;
if (!node->next[bit]) node->next[bit] = new TrieNode();
node = node->next[bit];
}
}
public:
int findMaximumXOR(vector<int>& A) {
TrieNode root;
for (int n : A) addNode(&root, n);
int ans = 0;
for (int n : A) {
auto node = &root;
int val = 0;
for (int i = 31; i >= 0; --i) {
int bit = (n >> i) & 1;
if (node->next[1 ^ bit]) {
val |= 1 << i;
node = node->next[1 ^ bit];
} else node = node->next[bit];
}
ans = max(ans, val);
}
return ans;
}
};
Solution 2.
// OJ: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
// Time: O(N)
// Space: O(N)
// Ref: https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
class Solution {
public:
int findMaximumXOR(vector<int>& A) {
unordered_set<int> s;
int mask = 0, ans = 0;
for (int i = 31; i >= 0; --i) {
mask |= 1 << i;
s.clear();
for (int n : A) s.insert(n & mask);
int next = ans | (1 << i);
for (int prefix : s) {
if (!s.count(next ^ prefix)) continue;
ans |= 1 << i;
break;
}
}
return ans;
}
};
Java
class Solution {
public int findMaximumXOR(int[] nums) {
int xor = 0;
int mask = 0;
for (int i = 31; i >= 0; i--) {
mask |= (1 << i);
Set<Integer> prefixSet = new HashSet<Integer>();
for (int num : nums)
prefixSet.add(mask & num);
int temp = xor | (1 << i);
for (int prefix : prefixSet) {
if (prefixSet.contains(prefix ^ temp)) {
xor = temp;
break;
}
}
}
return xor;
}
}