# XOR and Trie

In this article, I summarize two XOR related problems which can be solved by Trie.

# Problem 1

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

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