Welcome to Subscribe On Youtube
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 * 1040 <= 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;
}
};
-
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; } } ############ class Solution { public int findMaximumXOR(int[] numbers) { int max = 0; int mask = 0; for (int i = 30; i >= 0; i--) { int current = 1 << i; mask = mask ^ current; Set<Integer> set = new HashSet<>(); for (int j = 0, k = numbers.length; j < k; j++) { set.add(mask & numbers[j]); } int flag = max | current; for (Integer prefix : set) { if (set.contains(prefix ^ flag)) { max = flag; break; } } } return max; } } -
// 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 add(TrieNode *node, int n) { for (int i = 31; i >= 0; --i) { int b = n >> i & 1; if (node->next[b] == NULL) node->next[b] = new TrieNode(); node = node->next[b]; } } int maxXor(TrieNode *node, int n) { int ans = 0; for (int i = 31; i >= 0; --i) { int b = n >> i & 1; if (node->next[1 - b]) { // if we can go the opposite direction, do it. node = node->next[1 - b]; ans |= 1 << i; } else { node = node->next[b]; } } return ans; } public: int findMaximumXOR(vector<int>& A) { TrieNode root; int ans = 0; for (int n : A) { add(&root, n); ans = max(ans, maxXor(&root, n)); } return ans; } }; -
class Solution: def findMaximumXOR(self, nums: List[int]) -> int: max = 0 mask = 0 for i in range(30, -1, -1): current = 1 << i mask = mask ^ current s = set() for num in nums: s.add(num & mask) flag = max | current for prefix in s: if prefix ^ flag in s: max = flag break return max ############ class TrieNode(object): def __init__(self, bit=None): self.isWord = False self.word = None self.one = None self.zero = None count = 0 class Solution(object): def findMaximumXOR(self, nums): """ :type nums: List[int] :rtype: int """ def dfs(root, num, mask): if not root: return if mask == 0x00: self.ans = max(self.ans, root.word ^ num) return if mask & num: if root.zero: dfs(root.zero, num, mask >> 1) else: dfs(root.one, num, mask >> 1) else: if root.one: dfs(root.one, num, mask >> 1) else: dfs(root.zero, num, mask >> 1) if len(nums) < 2: return 0 root = TrieNode() self.ans = float("-inf") for num in nums: mask = 0x80000000 p = root for i in range(0, 32): node = None if num & mask: if not p.one: node = TrieNode() p.one = node else: node = p.one else: if not p.zero: node = TrieNode() p.zero = node else: node = p.zero p = node mask = mask >> 1 p.isWord = True p.word = num for num in nums: dfs(root, num, 0x80000000) return self.ans -
type Trie struct { children [26]*Trie } func newTrie() *Trie { return &Trie{} } func (this *Trie) insert(x int) { node := this for i := 30; i >= 0; i-- { v := (x >> i) & 1 if node.children[v] == nil { node.children[v] = newTrie() } node = node.children[v] } } func (this *Trie) search(x int) int { node := this res := 0 for i := 30; i >= 0; i-- { v := (x >> i) & 1 if node.children[v^1] != nil { res = res<<1 | 1 node = node.children[v^1] } else { res <<= 1 node = node.children[v] } } return res } func findMaximumXOR(nums []int) int { trie := newTrie() ans := 0 for _, v := range nums { trie.insert(v) ans = max(ans, trie.search(v)) } return ans } func max(a, b int) int { if a > b { return a } return b }