Maximum XOR of Two Numbers — Binary Trie

Problem

Find the maximum XOR of two numbers in nums.

Approach — Binary Trie (MSB to LSB)

Insert all numbers bit by bit (bit 31 to 0). For each number, traverse trie greedily choosing the opposite bit to maximize XOR.

Time: O(32n) | Space: O(32n)

Solutions

Python

class Solution:
    def findMaximumXOR(self, nums: list[int]) -> int:
        root={}
        for n in nums:
            node=root
            for bit in range(31,-1,-1):
                b=(n>>bit)&1
                if b not in node: node[b]={}
                node=node[b]
        ans=0
        for n in nums:
            node=root; xor=0
            for bit in range(31,-1,-1):
                b=(n>>bit)&1; want=1-b
                if want in node: xor=(xor<<1)|1; node=node[want]
                else: xor=(xor<<1); node=node[b]
            ans=max(ans,xor)
        return ans

C++

class Solution {
    struct Node{Node* ch[2]={nullptr,nullptr};};
    Node* root=new Node();
public:
    int findMaximumXOR(vector<int>& nums){
        for(int n:nums){
            Node* cur=root;
            for(int b=31;b>=0;b--){int bit=(n>>b)&1;if(!cur->ch[bit])cur->ch[bit]=new Node();cur=cur->ch[bit];}
        }
        int ans=0;
        for(int n:nums){
            Node* cur=root; int xr=0;
            for(int b=31;b>=0;b--){
                int bit=(n>>b)&1,want=1-bit;
                if(cur->ch[want]){xr=(xr<<1)|1;cur=cur->ch[want];}
                else{xr<<=1;cur=cur->ch[bit];}
            }
            ans=max(ans,xr);
        }
        return ans;
    }
};

Complexity

Time: O(32n) | Space: O(32n)