Log inSign up
mediumLeetCodeNot Started

Maximum XOR of Two Numbers

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

Given an integer array nums, return the maximum result of nums[i] ^ nums[j], where 0 <= i <= j < nums.length.

You must design an algorithm that runs in O(n) time complexity.

Example 1 · Example 1: Mixed Array:

Input: nums = [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28 (00101 ^ 11001 = 11100).

Example 2 · Example 2: Two Elements:

Input: nums = [14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70]
Output: 127
Explanation: The maximum XOR is achieved by picking suitable pairs yielding 127.

Constraints:

  • 1 <= nums.length <= 2 * 105
  • 0 <= nums[i] <= 231 - 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand how Binary 0/1 Tries solve pairwise bit-optimization problems.
  • Apply the greedy bit selection strategy from MSB to LSB.
  • Analyze the algebraic equivalence: a ^ b = c <=> a ^ c = b in prefix sets.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Maximize XOR between any two elements in an array.
  • Linear time constraint on pairwise bit combinations.
  • Bitwise prefix matching.

Algorithmic Decision Tree:

  • Build a 0/1 binary Trie containing all array numbers.
  • For each number, query the Trie for the maximum complementary path.

Connected Patterns:

TrieXOR Queries of a SubarraySingle Number

1. All Pairs Quadratic Search

Intuition

Use two nested loops to check all pairs (i, j). Compute nums[i] ^ nums[j] and update maxXor.

When to apply: When n <= 2000.

Algorithm

  1. Step 1: Set maxXor = 0.
  2. Step 2: Loop i from 0 to n - 1.
  3. Step 3: Loop j from i to n - 1.
  4. Step 4: maxXor = max(maxXor, nums[i] ^ nums[j]).
  5. Step 5: Return maxXor.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int findMaximumXORBrute(const vector<int>& nums) {
8 int maxXor = 0;
9 int n = nums.size();
10 for (int i = 0; i < n; ++i) {
11 for (int j = i; j < n; ++j) {
12 maxXor = max(maxXor, nums[i] ^ nums[j]);
13 }
14 }
15 return maxXor;
16}
17
18int main() {
19 vector<int> nums = {3, 10, 5, 25, 2, 8};
20 cout << "Brute: " << findMaximumXORBrute(nums) << endl; // 28
21 return 0;
22}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(1)

2. Bitwise Prefix Hash Set

Intuition

Iterate i from 30 down to 0. Create a mask = mask | (1 << i). Insert prefixes num & mask into a set. Propose candidate = maxXor | (1 << i). If any prefix exists in the set such that prefix ^ candidate is also in the set, we can achieve this bit, so set maxXor = candidate.

When to apply: When avoiding pointer-based Trie implementations.

Algorithm

  1. Step 1: Set maxXor = 0, mask = 0.
  2. Step 2: Loop i from 30 down to 0.
  3. Step 3: mask |= (1 << i). Set of prefixes = {num & mask for num in nums}.
  4. Step 4: candidate = maxXor | (1 << i).
  5. Step 5: If any prefix in set has (prefix ^ candidate) in set, maxXor = candidate.
  6. Step 6: Return maxXor.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4
5using namespace std;
6
7int findMaximumXORSet(const vector<int>& nums) {
8 int maxXor = 0;
9 int mask = 0;
10 for (int i = 30; i >= 0; --i) {
11 mask |= (1 << i);
12 unordered_set<int> prefixes;
13 for (int num : nums) {
14 prefixes.insert(num & mask);
15 }
16 int candidate = maxXor | (1 << i);
17 for (int prefix : prefixes) {
18 if (prefixes.count(prefix ^ candidate)) {
19 maxXor = candidate;
20 break;
21 }
22 }
23 }
24 return maxXor;
25}
26
27int main() {
28 vector<int> nums = {3, 10, 5, 25, 2, 8};
29 cout << "Prefix Set: " << findMaximumXORSet(nums) << endl; // 28
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(32 * n)
  • Space complexity: O(n)

3. Binary 0/1 Prefix Trie

Intuition

Build a Trie where each node has branches for 0 and 1. Insert all numbers into the Trie. For each number, traverse bit 30 down to 0. Greedily branch to 1 - bit if present; otherwise, take bit. This guarantees finding the maximum possible XOR pairing for each number in 31 steps.

When to apply: Optimal canonical solution for bitwise XOR matching.

Algorithm

  1. Step 1: Define TrieNode with children[0] and children[1].
  2. Step 2: Insert all numbers in nums into Trie from bit 30 down to 0.
  3. Step 3: For each number in nums, query Trie: if opposite bit exists, add (1 << i) and branch opposite; else branch same.
  4. Step 4: Return maximum query result found.

Binary Trie Search Trace: nums = [3, 10, 5, 25, 2, 8]

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Bit 4 (16): num = 5 has bit 0
Visual state
Values and pointers at this exact step
pointers
S
1
0
↑ XOR += 16
Check / comparison
Opposite bit 1 exists
Decision / next transition
Choose branch 1. XOR = 16.
Why this step matters

Bit 4 (16): num = 5 has bit 0. Desired bit is 1. Node has child 1 (from 25). Follow branch 1. Running XOR adds 16.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 struct TrieNode {
9 TrieNode* children[2] = {nullptr, nullptr};
10 };
11
12 TrieNode* root;
13
14 void insert(int num) {
15 TrieNode* curr = root;
16 for (int i = 30; i >= 0; --i) {
17 int bit = (num >> i) & 1;
18 if (!curr->children[bit]) {
19 curr->children[bit] = new TrieNode();
20 }
21 curr = curr->children[bit];
22 }
23 }
24
25 int getMaxXor(int num) {
26 TrieNode* curr = root;
27 int maxXor = 0;
28 for (int i = 30; i >= 0; --i) {
29 int bit = (num >> i) & 1;
30 int opposite = 1 - bit;
31 if (curr->children[opposite]) {
32 maxXor |= (1 << i);
33 curr = curr->children[opposite];
34 } else {
35 curr = curr->children[bit];
36 }
37 }
38 return maxXor;
39 }
40
41public:
42 int findMaximumXOR(vector<int>& nums) {
43 root = new TrieNode();
44 for (int x : nums) insert(x);
45 int res = 0;
46 for (int x : nums) {
47 res = max(res, getMaxXor(x));
48 }
49 return res;
50 }
51};
52
53int main() {
54 Solution sol;
55 vector<int> nums = {3, 10, 5, 25, 2, 8};
56 cout << "Optimal Trie: " << sol.findMaximumXOR(nums) << endl; // 28
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(31 * n)
  • Space complexity: O(31 * n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — All Pairs ComparisonO(n^2)O(1)Check every pair (nums[i], nums[j]) and track the maximum XOR.Quadratic pair generation.
2.Better — Bitwise Prefix Hash SetO(32 * n)O(n)Iterate from bit 30 down to 0, greedily guessing a 1 at bit i using a hash set of prefixes: a ^ target = b.Set rehashing across 31 levels.
3.Optimal — Binary 0/1 TrieOptimalO(31 * n)O(31 * n)Insert all numbers into a binary Trie. Query each number by greedily following opposite bit branches.Trie insertion and lookup.

Common Pitfalls & Crucial Edge Cases

O(n^2) nested loops

Checking all pairs takes O(n2) time and causes TLE when n = 2 * 105.

Starting bit traversal from bit 31 instead of 30 for non-negative integers

For non-negative integers, bit 31 is always 0.

Trie memory overhead

In languages with garbage collection, instantiating millions of small node objects can cause memory limits; use flat array-based Trie nodes for high speed.

Crucial Edge Cases to Validate:

  • Array of length 2 — Only one possible pair; return nums[0] ^ nums[1].
  • All numbers are identical (e.g. [5, 5, 5]) — Any pair XOR evaluates to 0.
  • Large numbers near 2^31 - 1 — Bit masks must properly account for up to 31 bits.
  • Zero in the array — Handled seamlessly by Trie root branch 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the greedy choice property: a set bit at position k is strictly greater than all set bits from 0 to k - 1 combined.
  2. Compare the Binary Trie approach with the Hash Set prefix masking approach: both achieve O(31 * N) time.
  3. Draw a small 3-bit Trie example (e.g. numbers 3, 5, 10, 25) to illustrate opposite branch traversal.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal greedy strategy to maximize the XOR of two numbers bit-by-bit from MSB to LSB?

2.How does a Binary Trie achieve O(n) time complexity for this problem?

3.How does the Hash Set prefix approach work without building an explicit Trie?

Back to DSA Sheet