Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Maximum XOR of Two Numbers in an Array

MEDIUMProblemSolveExternal Links

Description

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

The XOR (exclusive OR) of two integers compares their binary representations bit by bit: each result bit is 1 if the corresponding bits of the two operands differ, and 0 if they are the same. For example, 5 XOR 2 = 101 XOR 010 = 111 = 7.

Your goal is to find the pair of elements in the array whose XOR value is the largest possible.

Examples

Example 1

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

Output: 28

Explanation: The pair that produces the maximum XOR is 5 XOR 25. In binary: 5 = 00101 and 25 = 11001. XOR-ing bit by bit: 00101 XOR 11001 = 11100 = 28. No other pair in the array yields a higher XOR value.

Example 2

Input: nums = [5, 2, 6]

Output: 7

Explanation: In binary: 5 = 101, 2 = 010, 6 = 110. The XOR values for all pairs are: 5 XOR 2 = 111 = 7, 5 XOR 6 = 011 = 3, 2 XOR 6 = 100 = 4. The maximum is 7, achieved by the pair (5, 2).

Example 3

Input: nums = [7, 3, 1]

Output: 6

Explanation: In binary: 7 = 111, 3 = 011, 1 = 001. XOR pairs: 7 XOR 3 = 100 = 4, 7 XOR 1 = 110 = 6, 3 XOR 1 = 010 = 2. The maximum is 6 from the pair (7, 1). Notice that even though 7 has the most set bits, its best partner is 1 (not 3), because 7 and 1 differ the most in the higher bit positions.

Constraints

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

Editorial

Brute Force

Intuition

The simplest approach is to check every possible pair of numbers in the array, compute their XOR, and track the largest result.

Think of it like a round-robin tournament where every player plays against every other player. The "score" of each match is the XOR of the two players' values. We simply run all matches and report the highest score.

For an array of n elements, there are n×(n-1)/2 distinct pairs (since a XOR b = b XOR a, and a XOR a = 0 is never maximum for distinct elements). We compute XOR for each pair and keep the running maximum.

Step-by-Step Explanation

Let's trace through with nums = [5, 2, 6]:

Step 1: Initialize max_xor = 0. We will check all pairs.

Step 2: Pair (i=0, j=1): nums[0] XOR nums[1] = 5 XOR 2.

  • Binary: 101 XOR 010 = 111 = 7
  • 7 > 0 (current max) → Update max_xor = 7

Step 3: Pair (i=0, j=2): nums[0] XOR nums[2] = 5 XOR 6.

  • Binary: 101 XOR 110 = 011 = 3
  • 3 < 7 (current max) → No update. max_xor stays 7

Step 4: Pair (i=1, j=2): nums[1] XOR nums[2] = 2 XOR 6.

  • Binary: 010 XOR 110 = 100 = 4
  • 4 < 7 (current max) → No update. max_xor stays 7

Step 5: All pairs exhausted. Return max_xor = 7.

We checked 3 pairs total. The winning pair was (5, 2) with XOR = 7.

Algorithm

  1. Initialize max_xor = 0
  2. For each index i from 0 to n-2:
    • For each index j from i+1 to n-1:
      • Compute xor_val = nums[i] XOR nums[j]
      • If xor_val > max_xor, update 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 maxXor = 0;
        int n = nums.size();

        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:
        max_xor = 0
        n = len(nums)

        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 maxXor = 0;
        int n = nums.length;

        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 two nested loops generate n×(n-1)/2 pairs. For each pair, computing XOR is a single O(1) bitwise operation. Total: O(n²) comparisons.

Space Complexity: O(1)

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

Why This Approach Is Not Efficient

With n up to 2 × 10^5, the brute force performs approximately (2×10^5)² / 2 = 2 × 10^10 operations. This exceeds the typical time limit of ~10^8 operations per second by a factor of 200, making it far too slow.

The fundamental waste is that the brute force treats XOR as a black box — it doesn't exploit any structure of the XOR operation. But XOR has a critical property: the result is determined bit by bit, independently at each position. Bit position k of a XOR b depends only on bit k of a and bit k of b.

Furthermore, to maximize XOR, we want the highest-order bits to be 1 (since a 1 at bit position k contributes 2^k to the value). This means we should prioritize finding pairs that disagree at the most significant bit positions.

This bit-level structure is perfectly suited for a bitwise Trie — a tree where each level represents one bit position. By storing all numbers in a bitwise trie (from MSB to LSB), we can greedily choose the opposite bit at each level to maximize the XOR, reducing the per-query time from O(n) to O(32) = O(log M) where M is the maximum element value.

Optimal Approach - Bitwise Trie

Intuition

To maximize XOR, we want each bit of the result to be 1, starting from the most significant bit (MSB). A 1 at bit position k means the two numbers disagree at that position — one has 0 and the other has 1.

Imagine you are given a number and asked: "Which number in the array, when XOR'd with yours, gives the largest result?" The greedy strategy is:

  1. Look at the highest bit of your number
  2. If your bit is 0, you WANT a partner with bit 1 (to make the XOR bit 1)
  3. If your bit is 1, you WANT a partner with bit 0 (same reason)
  4. Repeat for each bit from high to low

At each bit position, you always prefer the opposite bit. If the opposite is available, take it (the XOR result bit is 1). If not, you are forced to take the same bit (the XOR result bit is 0).

A bitwise Trie makes this lookup efficient. Each number is stored as a path of bits from MSB to LSB. To find the best partner for a number, we traverse the trie greedily choosing the opposite branch at each level. This takes O(32) time per query — constant time regardless of array size.

Phase 1 (Build): Insert all numbers into the bitwise trie.
Phase 2 (Query): For each number, traverse the trie greedily to find its maximum XOR partner. Track the overall maximum.

Bitwise trie storing numbers 5 (101), 2 (010), and 6 (110) as 3-bit binary paths, with a query arrow showing greedy opposite-bit selection
Bitwise trie storing numbers 5 (101), 2 (010), and 6 (110) as 3-bit binary paths, with a query arrow showing greedy opposite-bit selection

Step-by-Step Explanation

Let's trace through with nums = [5, 2, 6] using 3-bit binary representations:

  • 5 = 101
  • 2 = 010
  • 6 = 110

Phase 1: Build the Trie

Step 1: Initialize an empty bitwise trie (just root).

Step 2: Insert 5 (101): Create path root → 1 → 0 → 1. Three new nodes created.

Step 3: Insert 2 (010): Create path root → 0 → 1 → 0. Root's left child '0' is new, then '1', then '0'. Three new nodes.

Step 4: Insert 6 (110): Start at root → 1 (already exists from 5). Then 1 → 1 is new. Then 1 → 0 is new. Two new nodes. The trie now has 8 nodes total.

Phase 2: Query Each Number

Step 5: Query for 5 (101). Try to pick opposite bits greedily:

  • Bit 2 = 1 → want 0. Root has child '0'? YES (from 2). Go to '0'. XOR bit = 1.
  • Bit 1 = 0 → want 1. Node '0' has child '1'? YES (from 2). Go to '1'. XOR bit = 1.
  • Bit 0 = 1 → want 0. Node '0→1' has child '0'? YES (from 2). Go to '0'. XOR bit = 1.
  • XOR = 111 = 7. Partner found: path 010 = 2. So 5 XOR 2 = 7.

Step 6: Query for 2 (010). Greedy opposite bits:

  • Bit 2 = 0 → want 1. Root has '1'? YES. Go to '1'. XOR bit = 1.
  • Bit 1 = 1 → want 0. Node '1' has '0'? YES (from 5). Go to '0'. XOR bit = 1.
  • Bit 0 = 0 → want 1. Node '1→0' has '1'? YES (from 5). Go to '1'. XOR bit = 1.
  • XOR = 111 = 7. Partner: 101 = 5. Same pair, same max.

Step 7: Query for 6 (110). Greedy opposite bits:

  • Bit 2 = 1 → want 0. Root has '0'? YES. Go to '0'. XOR bit = 1.
  • Bit 1 = 1 → want 0. Node '0' has '0'? NO — only has child '1'. MISS! Forced to go '1'. XOR bit = 0.
  • Bit 0 = 0 → want 1. Node '0→1' has '1'? NO — only has child '0'. MISS! Forced to go '0'. XOR bit = 0.
  • XOR = 100 = 4. Partner: 010 = 2. So 6 XOR 2 = 4. Less than 7.

Step 8: Maximum across all queries = max(7, 7, 4) = 7. Return 7.

Bitwise Trie — Build and Greedy Query for Maximum XOR — Watch how numbers are stored as binary paths in the trie, then see the greedy query pick opposite bits at each level to maximize XOR.

Algorithm

Phase 1 — Build the Bitwise Trie:

  1. Create a trie where each node has at most two children: 0 and 1
  2. For each number in the array:
    • Start at the root
    • For each bit from position 31 (MSB) down to 0 (LSB):
      • Extract the bit: bit = (num >> i) & 1
      • If the child for this bit doesn't exist, create it
      • Move to the child

Phase 2 — Query for Maximum XOR:
3. Initialize result = 0
4. For each number in the array:

  • Start at the root
  • Initialize current_xor = 0
  • For each bit from position 31 down to 0:
    • Extract the bit: bit = (num >> i) & 1
    • Compute the opposite: opp = 1 - bit
    • If the child for opp exists: take it, set this XOR bit to 1 (current_xor |= (1 << i))
    • Otherwise: take the child for bit (XOR bit stays 0)
  • Update result = max(result, current_xor)
  1. Return result

Code

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

struct TrieNode {
    TrieNode* children[2];
    TrieNode() {
        children[0] = nullptr;
        children[1] = nullptr;
    }
};

class Solution {
public:
    void insert(TrieNode* root, int num) {
        TrieNode* curr = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (curr->children[bit] == nullptr) {
                curr->children[bit] = new TrieNode();
            }
            curr = curr->children[bit];
        }
    }

    int getMaxXor(TrieNode* root, int num) {
        TrieNode* curr = root;
        int maxXor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int oppBit = 1 - bit;
            if (curr->children[oppBit] != nullptr) {
                maxXor |= (1 << i);
                curr = curr->children[oppBit];
            } else {
                curr = curr->children[bit];
            }
        }
        return maxXor;
    }

    int findMaximumXOR(vector<int>& nums) {
        TrieNode* root = new TrieNode();
        for (int num : nums) {
            insert(root, num);
        }

        int result = 0;
        for (int num : nums) {
            result = max(result, getMaxXor(root, num));
        }
        return result;
    }
};
class TrieNode:
    def __init__(self):
        self.children = [None, None]  # children[0] and children[1]

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

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

        def get_max_xor(num: int) -> int:
            curr = root
            max_xor = 0
            for i in range(31, -1, -1):
                bit = (num >> i) & 1
                opp_bit = 1 - bit
                if curr.children[opp_bit] is not None:
                    max_xor |= (1 << i)
                    curr = curr.children[opp_bit]
                else:
                    curr = curr.children[bit]
            return max_xor

        for num in nums:
            insert(num)

        result = 0
        for num in nums:
            result = max(result, get_max_xor(num))

        return result
class Solution {
    static class TrieNode {
        TrieNode[] children = new TrieNode[2];
    }

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

    private int getMaxXor(TrieNode root, int num) {
        TrieNode curr = root;
        int maxXor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int oppBit = 1 - bit;
            if (curr.children[oppBit] != null) {
                maxXor |= (1 << i);
                curr = curr.children[oppBit];
            } else {
                curr = curr.children[bit];
            }
        }
        return maxXor;
    }

    public int findMaximumXOR(int[] nums) {
        TrieNode root = new TrieNode();
        for (int num : nums) {
            insert(root, num);
        }

        int result = 0;
        for (int num : nums) {
            result = Math.max(result, getMaxXor(root, num));
        }
        return result;
    }
}

Complexity Analysis

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

The build phase inserts n numbers, each taking O(L) = O(32) time to traverse 32 bit levels. The query phase queries n numbers, each taking O(L) = O(32) time for the greedy traversal. Total: O(2 × n × 32) = O(n × L). Since L = 32 is a constant, this simplifies to O(n) in practice.

Compared to the brute force O(n²), for n = 200,000 this means ~6.4 million operations instead of ~20 billion — a 3000× improvement.

Space Complexity: O(n × L)

Each number creates at most L = 32 new trie nodes (in the worst case where it shares no prefix with existing numbers). With n numbers, the maximum number of nodes is O(n × L). Each node stores two pointers. In practice, many numbers share bit-prefixes, so the actual space is usually much less than the worst case.

For n = 200,000 and L = 32, the worst case is ~6.4 million nodes, which is very manageable in memory.