XOR and Trie

Problem 1

421. Maximum XOR of Two Numbers in an Array

Explanation

  • Each number is a 32 bits binary numbers
  • Organize the numbers in a tree and each node has two children: 0 and 1
  • The maximum XOR of a specified num can be found in the tree with the complexity of O(32)
In this example, we have 3 number: 0b00, 0b01, 0b11.

Code

class TrieNode{
public:
vector<TrieNode*> children;
TrieNode(){
children.assign(2, nullptr);
}
};
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
TrieNode* root = new TrieNode();
TrieNode* curr = root;
for (auto num: nums){
curr = root;
for (int bit = 31; bit >=0; --bit){
int thisBit = (num>>bit) & 1;
if (curr->children[thisBit] == nullptr){
TrieNode* next = new TrieNode();
curr->children[thisBit] = next;
}
curr = curr -> children[thisBit];
}
}
int ret = 0;
for (auto num : nums){
int thisRet = 0;
curr = root;
for (int bit = 31; bit >=0; --bit){
int thisBit = (num>>bit) & 1;
if (curr->children[1 - thisBit] != nullptr){
thisRet |= 1 << bit;
curr = curr -> children[1 - thisBit];
} else {
curr = curr -> children[thisBit];
}
}
ret = max(ret, thisRet);

}
return ret;
}
};

Problem 2

ACWing 3488 The maximum XOR sum

Explanation

This problem is the harder version for problem1. First, we need change it to problem1 by creating prefixsum style prefixXOR. Second, we have an extra constraint

Reference

[1]https://youtu.be/NpxCVxN4y70

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store