Home/Questions/Q 3527
Next
In Process

RTSALL Latest Articles

aarav0
Asked: 2026-09-11T09:52:32-05:00 In: ,

How does a 32-bit Binary Trie find the Maximum XOR of Two Numbers in O(N) time?

Given an integer array, we need to find two numbers whose bitwise XOR (A ^ B) is maximized.

The brute force approach tests all pairs in O(N^2), which is way too slow when N = 100,000. People recommend building a Binary Trie (prefix tree of bits 0 and 1) to solve this in O(32 * N) = O(N) time. How does walking down a binary tree yield the maximum possible XOR?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Abhay Tiwari
    Begginer

    The Maximum XOR problem is the ultimate showcase of how bit manipulation and trees blend together. Once you see the greedy nature of binary numbers, the Binary Trie solution becomes second nature.

    1. The Greedy Bit Principle

    In binary numbers, the Most Significant Bit (MSB) has more numerical value than all lower bits combined! For example, bit 30 ($2^{30} pprox 1.07 imes 10^9$) is strictly greater than the sum of all bits from 0 to 29 combined ($2^{30} – 1$).

    Therefore, to maximize an XOR sum, you must be greedy from left to right (MSB down to LSB):

    • If the current bit of number num is 1, you desperately want to pair it with a number whose corresponding bit is 0 (because 1 ^ 0 = 1).
    • If the current bit of num is 0, you want to pair it with a number whose corresponding bit is 1 (because 0 ^ 1 = 1).

    2. Why a Binary Trie?

    A Binary Trie is just a tree where every node has at most two children: 0 (left) and 1 (right).

    1. Insert: You insert each number into the Trie as a 31-bit or 32-bit string of binary digits, from bit 31 down to bit 0.
    2. Query: For each number x, you walk down the Trie. At each bit b, you ask: ‘Does the opposite branch (1 - b) exist?’
      • If YES: Take that branch! That bit in your XOR result becomes 1.
      • If NO: You’re forced to take the same branch (b), so that bit in your XOR result becomes 0.

    Because you made the best possible choice at every single bit position starting from the highest power of 2, the final accumulated number is mathematically guaranteed to be the global maximum XOR!

    Clean Python 3.12 Implementation

    class TrieNode:
    __slots__ = ('children',)
    def __init__(self):
        self.children: list[TrieNode | None] = [None, None]

class Solution:
    def find_maximum_xor(self, nums: list[int]) -> int:
        root = TrieNode()

        # Step 1: Insert all numbers into the 31-bit binary trie
        for num in nums:
            curr = root
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                if not curr.children[bit]:
                    curr.children[bit] = TrieNode()
                curr = curr.children[bit]

        # Step 2: Query each number against the trie
        max_xor = 0
        for num in nums:
            curr = root
            current_xor = 0
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                opposite_bit = 1 - bit
                
                # Greedily check if the complementary bit exists
                if curr.children[opposite_bit]:
                    current_xor |= (1 << i)
                    curr = curr.children[opposite_bit]
                else:
                    curr = curr.children[bit]
                    
            max_xor = max(max_xor, current_xor)

        return max_xor

    Complexity Breakdown

    • Time Complexity: O(31 * N) = O(N). Inserting N numbers takes 31 * N operations. Querying N numbers takes 31 * N operations. Total time is strictly linear in the number of elements.
    • Space Complexity: O(31 * N) worst-case node allocations. In practice, prefix branches overlap heavily, keeping memory around a few megabytes.
    • 0
  2. Abhishek
    Begginer

    Here is the C++20 Binary Trie implementation. To avoid dynamic heap allocations during tree insertion, we use a flat contiguous node pool.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <vector>
#include <algorithm>

class BinaryTrie {
    struct Node {
        int next[2] = {-1, -1};
    };
    std::vector<Node> tree;

public:
    BinaryTrie() {
        tree.emplace_back(); // Root node at index 0
    }

    void insert(int num) {
        int curr = 0;
        for (int i = 30; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (tree[curr].next[bit] == -1) {
                tree[curr].next[bit] = tree.size();
                tree.emplace_back();
            }
            curr = tree[curr].next[bit];
        }
    }

    int queryMaxXOR(int num) const {
        int curr = 0;
        int max_xor = 0;
        for (int i = 30; i >= 0; --i) {
            int bit = (num >> i) & 1;
            int opposite = 1 - bit;
            if (tree[curr].next[opposite] != -1) {
                max_xor |= (1 << i);
                curr = tree[curr].next[opposite];
            } else {
                curr = tree[curr].next[bit];
            }
        }
        return max_xor;
    }
};

int findMaximumXOR(const std::vector<int>& nums) {
    BinaryTrie trie;
    for (int x : nums) trie.insert(x);

    int ans = 0;
    for (int x : nums) {
        ans = std::max(ans, trie.queryMaxXOR(x));
    }
    return ans;
}

int main() {
    std::vector<int> nums = {3, 10, 5, 25, 2, 8};
    std::cout << "Maximum XOR Pair: " << findMaximumXOR(nums) << "n"; // Expected: 28 (5 ^ 25)
    return 0;
}

    Complexity: Strictly O(31 * N) = O(N) time with flat memory pooling.

    • 0