XOR and Trie

In this article, I summarize two XOR related problems which can be solved by 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