Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Bitwise Foundations for Tries

HARDProblemSolveExternal Links

Description

Given an array of non-negative integers nums, find the maximum XOR value obtainable by selecting any two elements from the array.

The XOR (exclusive OR) of two numbers compares their binary representations bit by bit: it produces a 1 at each bit position where the two numbers differ, and a 0 where they are the same.

Formally, return the maximum value of nums[i] XOR nums[j] for all valid pairs 0 ≤ i ≤ j < n, where n is the length of the array.

This problem introduces the concept of a binary trie (bitwise trie) — a trie where each node has at most two children (representing bits 0 and 1), and each path from root to leaf represents a number's binary form. Understanding this structure is foundational for many advanced bit manipulation problems.

Examples

Example 1

Input: nums = [3, 10, 5, 25, 2, 8]

Output: 28

Explanation:

  • 5 in binary is 00101 and 25 in binary is 11001.
  • 5 XOR 25 = 00101 XOR 11001 = 11100 = 28.
  • No other pair produces a larger XOR value. The key observation is that 5 and 25 differ at the highest bit positions (bits 4 and 3), which contributes the most to the result.

Example 2

Input: nums = [8, 10, 2]

Output: 10

Explanation:

  • 8 in binary is 1000 and 2 in binary is 0010.
  • 8 XOR 2 = 1000 XOR 0010 = 1010 = 10.
  • Other pairs: 8 XOR 10 = 1000 XOR 1010 = 0010 = 2, and 10 XOR 2 = 1010 XOR 0010 = 1000 = 8. The maximum is 10.

Example 3

Input: nums = [0]

Output: 0

Explanation: With only one element, the only valid pair is (0, 0), giving 0 XOR 0 = 0.

Constraints

  • 1 ≤ nums.length ≤ 2 × 10^5
  • 0 ≤ nums[i] ≤ 2^31 - 1

Editorial

Brute Force

Intuition

The most straightforward approach is to try every possible pair of numbers in the array and compute their XOR. We keep track of the largest XOR value seen across all pairs.

Think of it like a round-robin tournament: every player plays against every other player. We record the score (XOR value) of each match and declare the highest score the winner. With n players, there are n × (n-1) / 2 matches to play.

This guarantees correctness because we exhaustively check every possibility, but it gets very slow as the array grows.

Step-by-Step Explanation

Let's trace through with nums = [3, 5, 8]:

In binary (using 4 bits): 3 = 0011, 5 = 0101, 8 = 1000

Step 1: Initialize max_xor = 0.

Step 2: Fix i = 0 (nums[0] = 3). Start checking pairs with j > i.

Step 3: Pair (i=0, j=1): 3 XOR 5 = 0011 XOR 0101 = 0110 = 6.

  • Is 6 > max_xor (0)? Yes. Update max_xor = 6.

Step 4: Pair (i=0, j=2): 3 XOR 8 = 0011 XOR 1000 = 1011 = 11.

  • Is 11 > max_xor (6)? Yes. Update max_xor = 11.

Step 5: Fix i = 1 (nums[1] = 5). Check remaining pairs.

Step 6: Pair (i=1, j=2): 5 XOR 8 = 0101 XOR 1000 = 1101 = 13.

  • Is 13 > max_xor (11)? Yes. Update max_xor = 13.

Step 7: All pairs checked. Return max_xor = 13.

Brute Force — Checking All XOR Pairs — Watch how the brute force examines every pair of numbers, computing their XOR and tracking the maximum value found so far.

Algorithm

  1. Initialize max_xor = 0
  2. For each index i from 0 to n-1:
    • For each index j from i to n-1:
      • Compute xor_val = nums[i] XOR nums[j]
      • Update max_xor = max(max_xor, xor_val)
  3. Return max_xor

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int n = nums.size();
        int maxXor = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                maxXor = max(maxXor, nums[i] ^ nums[j]);
            }
        }
        return maxXor;
    }
};
class Solution:
    def findMaximumXOR(self, nums: list[int]) -> int:
        n = len(nums)
        max_xor = 0
        for i in range(n):
            for j in range(i + 1, n):
                max_xor = max(max_xor, nums[i] ^ nums[j])
        return max_xor
class Solution {
    public int findMaximumXOR(int[] nums) {
        int n = nums.length;
        int maxXor = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                maxXor = Math.max(maxXor, nums[i] ^ nums[j]);
            }
        }
        return maxXor;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times, and the inner loop runs up to n-1 times for each outer iteration. Total pair comparisons: n × (n-1) / 2, which simplifies to O(n²). Each XOR operation is O(1) on modern hardware.

Space Complexity: O(1)

We only use a single variable max_xor to track the result. No additional data structures are allocated.

Why This Approach Is Not Efficient

With n up to 2 × 10^5, the brute force performs:

(2 × 10^5) × (2 × 10^5 - 1) / 2 ≈ 2 × 10^10 pair comparisons

This far exceeds the typical limit of ~10^8 operations per second, making it orders of magnitude too slow.

The fundamental waste is that we treat each pair independently. We compute 3 XOR 5, then 3 XOR 8, then 5 XOR 8 — never leveraging the fact that these numbers share common bit patterns. If we already know that 8 starts with bit 1 and 5 starts with bit 0, their XOR at the highest bit is guaranteed to be 1 (which is good for maximizing!). We should not need to recheck lower-significance bits of less promising pairs.

The key insight is: to maximize XOR, we should greedily maximize the result starting from the most significant bit. A bit at position k contributes 2^k to the result, so getting a 1 at position 30 is worth more than getting 1s at all positions 0 through 29 combined.

We need a data structure that stores numbers by their binary representation and lets us greedily pick opposite bits from the most significant position downward. This is exactly what a binary trie provides.

Optimal Approach - Binary Trie (Bitwise Trie)

Intuition

A binary trie is a trie where each node has at most two children: one for bit 0 and one for bit 1. Each number is inserted as a sequence of bits from the most significant bit (MSB) down to the least significant bit (LSB).

After inserting all numbers, the trie encodes every number's binary representation as a path from root to leaf. To find the maximum XOR partner for a number, we traverse the trie greedily:

  • At each bit position, we prefer to go to the opposite branch. If the current number has bit 0 at this position, we try to go to the 1-branch, and vice versa.
  • Why? Because XOR produces 1 when bits differ. By choosing the opposite bit at each level, we maximize the XOR contribution at that bit position.
  • If the opposite branch does not exist, we are forced to follow the same-bit branch (contributing 0 to the XOR at that position).

Imagine you are building a number digit by digit (in binary), from the highest to the lowest position. At each position you ask: "Can I make this bit a 1 in my XOR result?" If the trie has a path with the opposite bit, the answer is yes. You always prioritize higher bits because bit position 30 contributes 2^30 ≈ 10^9, while bit position 0 contributes just 1.

This greedy strategy guarantees the maximum XOR because:

  1. We process bits from MSB to LSB (most valuable first)
  2. At each bit, we maximize locally (choose opposite if possible)
  3. Higher-bit decisions always outweigh lower-bit decisions, so greedy is optimal.
Binary trie storing numbers 3 (0011), 5 (0101), and 8 (1000) with paths from root to leaves, showing how opposite-bit traversal maximizes XOR
Binary trie storing numbers 3 (0011), 5 (0101), and 8 (1000) with paths from root to leaves, showing how opposite-bit traversal maximizes XOR

Step-by-Step Explanation

Let's trace with nums = [3, 5, 8] using 4-bit representation:

3 = 0011, 5 = 0101, 8 = 1000

Phase 1: Build the Binary Trie

Step 1: Initialize an empty binary trie (root node only).

Step 2: Insert 3 (0011) — create path: root → 0 → 0 → 1 → 1.

Step 3: Insert 5 (0101) — create path: root → 0 → 1 → 0 → 1.

  • Node at bit 3 already has child '0', so we reuse it. At bit 2, we branch: 3 went to '0', but 5 goes to '1'. New nodes are created for the diverging path.

Step 4: Insert 8 (1000) — create path: root → 1 → 0 → 0 → 0.

  • Bit 3 is '1' — completely new branch. All nodes are newly created.

Phase 2: Search for Maximum XOR

Step 5: Search for max XOR partner of 3 (0011):

  • Bit 3: 3 has 0, want 1. Children[1] exists (8's path). Take it! XOR bit = 1.
  • Bit 2: 3 has 0, want 1. At 8's path, only children[0] exists. Forced same. XOR bit = 0.
  • Bit 1: 3 has 1, want 0. Children[0] exists. Take it! XOR bit = 1.
  • Bit 0: 3 has 1, want 0. Children[0] exists. Take it! XOR bit = 1.
  • Result: 1011 = 11 (this is 3 XOR 8 = 11).

Step 6: Search for max XOR partner of 5 (0101):

  • Bit 3: 5 has 0, want 1. Children[1] exists (8's path). Take it! XOR bit = 1.
  • Bit 2: 5 has 1, want 0. Children[0] exists. Take it! XOR bit = 1.
  • Bit 1: 5 has 0, want 1. Only children[0] exists. Forced same. XOR bit = 0.
  • Bit 0: 5 has 1, want 0. Children[0] exists. Take it! XOR bit = 1.
  • Result: 1101 = 13 (this is 5 XOR 8 = 13).

Step 7: Search for max XOR partner of 8 (1000):

  • Bit 3: 8 has 1, want 0. Children[0] exists (3 and 5's paths). Take it! XOR bit = 1.
  • Bit 2: 8 has 0, want 1. Children[1] exists (5's path). Take it! XOR bit = 1.
  • Bit 1: 8 has 0, want 1. Only children[0] exists. Forced same. XOR bit = 0.
  • Bit 0: 8 has 0, want 1. Children[1] exists. Take it! XOR bit = 1.
  • Result: 1101 = 13 (this is 8 XOR 5 = 13).

Step 8: Maximum across all searches: max(11, 13, 13) = 13. Return 13.

Binary Trie — Insert Numbers and Greedy XOR Search — Watch how numbers are inserted as bit-paths into the binary trie, then see the greedy opposite-bit strategy find the maximum XOR partner.

Algorithm

Binary Trie Node structure: Each node has exactly two child pointers: children[0] and children[1].

Phase 1: Build the Trie

  1. For each number in the array:
    • Starting from bit position 30 (MSB for 31-bit integers) down to bit position 0 (LSB):
      • Extract the current bit: bit = (num >> position) & 1
      • If children[bit] does not exist, create a new node
      • Move to children[bit]

Phase 2: Search for Maximum XOR
2. For each number in the array:

  • Initialize xor_result = 0
  • Starting from bit position 30 down to 0:
    • Extract the current bit: bit = (num >> position) & 1
    • Compute the opposite bit: opposite = bit XOR 1
    • If children[opposite] exists:
      • Take the opposite path (maximizes XOR at this position)
      • Set the corresponding bit in the result: xor_result |= (1 << position)
    • Else:
      • Take the same-bit path (no choice, XOR bit is 0 at this position)
  1. Track the maximum xor_result across all searches
  2. Return the maximum

Code

class TrieNode {
public:
    TrieNode* children[2];
    TrieNode() {
        children[0] = nullptr;
        children[1] = nullptr;
    }
};

class Solution {
private:
    TrieNode* root;

    void insert(int num) {
        TrieNode* node = root;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node->children[bit] == nullptr) {
                node->children[bit] = new TrieNode();
            }
            node = node->children[bit];
        }
    }

    int search(int num) {
        TrieNode* node = root;
        int xorResult = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int opposite = bit ^ 1;
            if (node->children[opposite] != nullptr) {
                xorResult |= (1 << i);
                node = node->children[opposite];
            } else {
                node = node->children[bit];
            }
        }
        return xorResult;
    }

public:
    int findMaximumXOR(vector<int>& nums) {
        root = new TrieNode();
        for (int num : nums) {
            insert(num);
        }
        int maxXor = 0;
        for (int num : nums) {
            maxXor = max(maxXor, search(num));
        }
        return maxXor;
    }
};
class TrieNode:
    def __init__(self):
        self.children = [None, None]


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

        def insert(num: int) -> None:
            node = root
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                if node.children[bit] is None:
                    node.children[bit] = TrieNode()
                node = node.children[bit]

        def search(num: int) -> int:
            node = root
            xor_result = 0
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                opposite = bit ^ 1
                if node.children[opposite] is not None:
                    xor_result |= (1 << i)
                    node = node.children[opposite]
                else:
                    node = node.children[bit]
            return xor_result

        for num in nums:
            insert(num)

        max_xor = 0
        for num in nums:
            max_xor = max(max_xor, search(num))
        return max_xor
class TrieNode {
    TrieNode[] children;
    TrieNode() {
        children = new TrieNode[2];
    }
}

class Solution {
    private TrieNode root;

    private void insert(int num) {
        TrieNode node = root;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.children[bit] == null) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
        }
    }

    private int search(int num) {
        TrieNode node = root;
        int xorResult = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int opposite = bit ^ 1;
            if (node.children[opposite] != null) {
                xorResult |= (1 << i);
                node = node.children[opposite];
            } else {
                node = node.children[bit];
            }
        }
        return xorResult;
    }

    public int findMaximumXOR(int[] nums) {
        root = new TrieNode();
        for (int num : nums) {
            insert(num);
        }
        int maxXor = 0;
        for (int num : nums) {
            maxXor = Math.max(maxXor, search(num));
        }
        return maxXor;
    }
}

Complexity Analysis

Time Complexity: O(n × L) where L = 31 (number of bits)

  • Building the trie: We insert n numbers, each requiring L bit-level operations. Total: O(n × L).
  • Searching for maximum XOR: We search for n numbers, each requiring L bit-level operations. Total: O(n × L).
  • Combined: O(n × L) + O(n × L) = O(n × L).
  • Since L = 31 is a fixed constant for 32-bit integers, this simplifies to O(n) — a massive improvement over the O(n²) brute force.
  • For n = 2 × 10^5: we perform about 2 × 10^5 × 31 × 2 ≈ 1.2 × 10^7 operations, well within time limits.

Space Complexity: O(n × L)

In the worst case, every number follows a unique bit path, creating n × L nodes in the trie. Each node stores two child pointers. With n = 2 × 10^5 and L = 31, that is about 6 × 10^6 nodes — manageable in memory.

In practice, numbers sharing common high-bit prefixes share trie nodes, so the actual space is often much less than the worst case.