L6. Maximum XOR of Two Numbers in an Array | C++ | Java

Mastering the Trie data structure for bit manipulation problems, specifically finding the maximum XOR pair between two distinct arrays or within a single array.

1. Why Do We Need This? (Problem Statement & Status Quo)

The Core Problem

You are given two arrays of non-negative integers: Array 1 and Array 2. Your task is to find the maximum possible value of $A \oplus B$ , where $A$ is chosen from Array 1 and $B$ is chosen from Array 2, and $\oplus$ represents the bitwise XOR operation.

Example Walkthrough

Array 1: [6, 8]
Array 2: [7, 8, 2]
Possible Pairs & XOR Values:
- $8 \oplus 7 = 15$
- $8 \oplus 8 = 0$
- $8 \oplus 2 = 10$
- $6 \oplus 7 = 1$
- $6 \oplus 8 = 14$
- $6 \oplus 2 = 4$
Maximum Result: Choosing $8$ from Array 1 and $7$ from Array 2 yields $8 \oplus 7 = \mathbf{15}$ .

Naive vs. Optimal Approach

Naive Approach ( $O(N \times M)$ ): Nested loops checking every element in Array 1 against every element in Array 2. For large datasets ( $N, M \approx 10^5$ ), this results in $O(N \times M)$ operations, leading to Time Limit Exceeded (TLE).
Optimal Trie Approach ( $O((N + M) \times 32)$ ): Store all elements of Array 1 in a binary Trie, then query each element of Array 2 against the Trie to greedily find its maximum XOR partner in near-linear time.

2. Core Mental Model & The Bitwise Greedy Intuition

Real-Life Analogy & Mental Hook

Think of the Trie as a digital sorting office where numbers are broken down into their binary digits (bits) from left to right (most significant bit to least significant bit). When searching for a number to maximize XOR with $X$ , you navigate down the Trie paths. At every bit position, you greedily want to take the exact opposite bit (if your bit is 0, you want a 1; if your bit is 1, you want a 0) because $1 \oplus 0 = 1$ or $0 \oplus 1 = 1$ , which sets that power of 2 in your final result. Setting higher powers of 2 first guarantees the maximum possible numerical value.

3. Simplifying the Problem: Array vs. Single Number $X$

Before solving the two-array problem, we must master its foundational prerequisite:

Given an array of numbers and a single integer $X$ , find the maximum value of $(\text{array}[i] \oplus X)$ .

If you understand this helper problem by heart, any advanced XOR-Trie problem becomes a trivial extension. The two-step recipe is:

Insert all numbers from the array into a binary Trie in their 32-bit binary representation.
Query the Trie with $X$ bit-by-bit to greedily construct the maximum possible XOR value.

4. Storing Integers as Binary Strings in a Trie

Computers store integers as 32-bit binary numbers. For compact explanation, let us represent numbers using 5 bits (e.g., $9 = 01001_2$ ).

Trie Node Structure

Each Trie node requires two child links (pointers):

links[0]: points to the child node for bit 0.
links[1]: points to the child node for bit 1.

CODE

          Root Node
         /         \
   links[0]      links[1]

Step-by-Step Insertion Example

Let us insert numbers: 9, 8, 7, 5, and 4 (using 5-bit binary representation).

Insert 9 ( $01001_2$ ):
- Start at root. Bit 0 $\rightarrow$ create reference pointer 0. Move to it.
- Bit 1 $\rightarrow$ create reference pointer 1. Move to it.
- Bit 0 $\rightarrow$ create reference pointer 0. Move to it.
- Bit 0 $\rightarrow$ create reference pointer 0. Move to it.
- Bit 1 $\rightarrow$ create reference pointer 1. Move to it.
Insert 8 ( $01000_2$ ):
- Bit 0 $\rightarrow$ already exists, move to it.
- Bit 1 $\rightarrow$ already exists, move to it.
- Bit 0 $\rightarrow$ already exists, move to it.
- Bit 0 $\rightarrow$ already exists, move to it.
- Bit 0 $\rightarrow$ does not exist! Create reference pointer 0.

5. The Greedy Query Algorithm (Getting Maximum XOR)

Let $X = 8$ ( $01000_2$ ) and we want to find the number in our Trie that maximizes $X \oplus \text{target}$ .

We start from the most significant bit (index 31 down to 0, or index 4 down to 0 in our 5-bit example).
For each bit of $X$ $X$ , we check if the opposite bit exists in the Trie node:
- If opposite exists: We take the opposite branch. This guarantees a 1 at this bit position in our XOR result, and we add $2^i$ to our running maximum.
- If opposite does NOT exist: We are forced to take the same bit branch, resulting in a 0 at this bit position in our XOR result.

Structure & Concept Flow

X = 8 (01000)

+-- Bit 4 (0): Look for opposite (1). Exists? Yes -> Go to 1, add 2^4 (16)

+-- Bit 3 (1): Look for opposite (0). Exists? Yes -> Go to 0, add 2^3 (8)

+-- Bit 2 (0): Look for opposite (1). Exists? Yes -> Go to 1, add 2^2 (4)

+-- Bit 1 (0): Look for opposite (1). Exists? Yes -> Go to 1, add 2^1 (2)

+-- Bit 0 (0): Look for opposite (1). Exists? Yes -> Go to 1, add 2^0 (1)

Result = 16 + 8 + 4 + 2 + 1 = 31 (or 15 depending on prefix paths).

6. Extending to Two Arrays

To solve the original problem (Maximum XOR of one element from Array 1 and one from Array 2):

Insert all elements of Array 1 into our binary Trie.
Initialize maxSoFar = 0.
Iterate through every element $Y$ in Array 2.
Query the Trie using $Y$ to find the maximum possible XOR value obtainable with any element in Array 1.
Update maxSoFar = max(maxSoFar, currentQueryResult).
Return maxSoFar.

Structure & Concept Flow

Array 1 elements ---> Inserted into Binary Trie

Array 2 elements ---> Iterated one by one ---> Queried against Trie ---> Track Max XOR

7. Complete Implementation (C++ and Java)

C++ Implementation

C++

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    Node* links[2];

    bool containsKey(int bit) {
        return (links[bit] != NULL);
    }

    Node* get(int bit) {
        return links[bit];
    }

    void put(int bit, Node* node) {
        links[bit] = node;
    }
};

class Trie {
private:
    Node* root;

public:
    Trie() {
        root = new Node();
    }

    void insert(int num) {
        Node* node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!node->containsKey(bit)) {
                node->put(bit, new Node());
            }
            node = node->get(bit);
        }
    }

    int getMax(int num) {
        Node* node = root;
        int maxNum = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int oppositeBit = 1 - bit;
            if (node->containsKey(oppositeBit)) {
                maxNum = maxNum | (1 << i);
                node = node->get(oppositeBit);
            } else {
                node = node->get(bit);
            }
        }
        return maxNum;
    }
};

class Solution {
public:
    int findMaximumXOR(vector<int>& nums1, vector<int>& nums2) {
        Trie trie;
        for (int& it : nums1) {
            trie.insert(it);
        }
        int maxXor = 0;
        for (int& it : nums2) {
            maxXor = max(maxXor, trie.getMax(it));
        }
        return maxXor;
    }
};

Java Implementation

JAVA

class Node {
    Node[] links = new Node[2];

    boolean containsKey(int bit) {
        return links[bit] != null;
    }

    Node get(int bit) {
        return links[bit];
    }

    void put(int bit, Node node) {
        links[bit] = node;
    }
}

class Trie {
    private static Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(int num) {
        Node node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!node.containsKey(bit)) {
                node.put(bit, new Node());
            }
            node = node.get(bit);
        }
    }

    public int getMax(int num) {
        Node node = root;
        int maxNum = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int oppositeBit = 1 - bit;
            if (node.containsKey(oppositeBit)) {
                maxNum = maxNum | (1 << i);
                node = node.get(oppositeBit);
            } else {
                node = node.get(bit);
            }
        }
        return maxNum;
    }
}

class Solution {
    public int findMaximumXOR(int[] nums1, int[] nums2) {
        Trie trie = new Trie();
        for (int val : nums1) {
            trie.insert(val);
        }
        int maxXor = 0;
        for (int val : nums2) {
            maxXor = Math.max(maxXor, trie.getMax(val));
        }
        return maxXor;
    }
}

8. Complexity Analysis

Operation / Metric	Complexity	Explanation
Time Complexity (Insertion)	$O(N \times 32)$	For each of the $N$ numbers in Array 1, we traverse 32 bits from left to right.
Time Complexity (Query)	$O(M \times 32)$	For each of the $M$ numbers in Array 2, we traverse 32 bits to find its optimal XOR pair.
Total Time Complexity	$O((N + M) \times 32)$	Extremely efficient; easily passes within standard time limits ( $N, M \leq 10^5$ ).
Space Complexity	$O(N \times 32)$	In the worst case, each inserted number creates 32 new nodes (though heavy prefix overlap reduces actual memory usage in practice).

Summary and Key Takeaways

Bit Manipulation Foundation: Solving XOR problems efficiently requires viewing integers as fixed-length binary strings (32 bits) rather than atomic numerical values.
Greedy Bit Selection: To maximize XOR results, always prioritize matching the most significant bits with their opposite bit (1 - bit).
Trie as a Bit Search Engine: A binary Trie replaces brute-force $O(N \times M)$ searches with logarithmic bit-path navigations ( $O(32)$ per lookup).
Class Design Best Practices: Encapsulating node operations (containsKey, get, put) and Trie methods (insert, getMax) inside well-defined classes produces clean, maintainable, and interview-ready code.
Extensibility: The single-array maximum XOR problem and the two-array variation share the exact same underlying Trie infrastructure.

L6. Maximum XOR of Two Numbers in an Array | C++ | Java

L6. Maximum XOR of Two Numbers in an Array | C++ | Java

1. Why Do We Need This? (Problem Statement & Status Quo)

The Core Problem

Example Walkthrough

Naive vs. Optimal Approach

2. Core Mental Model & The Bitwise Greedy Intuition

Real-Life Analogy & Mental Hook

3. Simplifying the Problem: Array vs. Single Number XXX

4. Storing Integers as Binary Strings in a Trie

Trie Node Structure

Step-by-Step Insertion Example

5. The Greedy Query Algorithm (Getting Maximum XOR)

6. Extending to Two Arrays

7. Complete Implementation (C++ and Java)

C++ Implementation

Java Implementation

8. Complexity Analysis

Summary and Key Takeaways

3. Simplifying the Problem: Array vs. Single Number $X$