# XOR and Trie

2 min readJul 21, 2021

--

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)

## 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