Course4all

Maximum XOR of Two Numbers in an Array

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Bit Manipulation.

Maximum XOR of Two Numbers in an Array

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0≤i≤j<n0 \leq i \leq j < n.
Medium

Examples

Input: nums = [3,10,5,25,2,8]
Output: 28
Approach 1

Level I: Brute Force (All Pairs)

Intuition

Check every possible pair of numbers (i,j)(i, j) and calculate their XOR sum. Track the maximum value found.

Thought Process

  1. Initialize maxResult = 0.
  2. Nested loop through nums.
  3. maxResult = max(maxResult, nums[i] ^ nums[j]).
  4. Return maxResult.

Pattern: Double Iteration

⏱ O(N^2) - Where $N$ is the number of elements in the array.💾 O(1) - Constant space.
java
public class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                max = Math.max(max, nums[i] ^ nums[j]);
            }
        }
        return max;
    }
}
Approach 2

Level II: Greedy Comparison with Hash Set

Intuition

We can build the maximum XOR bit by bit. For each bit position ii (from MSB to LSB), we check if there exists a pair of numbers whose ii-th bits could potentially form a better maximum XOR than what we have found so far.
⏱ $O(N \cdot 32)$💾 $O(N)$
java
class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        for (int i = 30; i >= 0; i--) {
            mask |= (1 << i);
            Set<Integer> set = new HashSet<>();
            for (int n : nums) set.add(n & mask);
            int tmp = max | (1 << i);
            for (int prefix : set) {
                if (set.contains(tmp ^ prefix)) {
                    max = tmp;
                    break;
                }
            }
        }
        return max;
    }
}
Approach 3

Level III: Optimal (Binary Trie)

Intuition

To maximize XOR, for each number XX, we want to find another number YY such that they have different bits at the highest possible positions. A Trie (Prefix Tree) storing binary representations allows us to greedily find the bitwise opposite at each step.

Thought Process

  1. Insert all numbers into a Trie of depth 31.
  2. For each number XX:
    • Start at the Trie root.
    • For each bit bb of XX (from MSB to LSB):
      • If we want bit 1−b1-b and it exists in the Trie, move there and add (1<<bit)(1 << bit) to our current XOR.
      • Else, move to the child with bit bb.
  3. Track the best XOR found for any XX.

Pattern: Bitwise Greedy with Trie

⏱ O(N \cdot 32) - Linear pass to build Trie and another to query.💾 O(N \cdot 32) - Store numbers bit-by-bit in Trie nodes.
java
class TrieNode {
    TrieNode[] children = new TrieNode[2];
}

public class Solution {
    public int findMaximumXOR(int[] nums) {
        TrieNode root = new TrieNode();
        for (int n : nums) {
            TrieNode curr = root;
            for (int i = 30; i >= 0; i--) {
                int bit = (n >> i) & 1;
                if (curr.children[bit] == null) curr.children[bit] = new TrieNode();
                curr = curr.children[bit];
            }
        }
        
        int max = 0;
        for (int n : nums) {
            TrieNode curr = root;
            int currSum = 0;
            for (int i = 30; i >= 0; i--) {
                int bit = (n >> i) & 1;
                if (curr.children[1 - bit] != null) {
                    currSum |= (1 << i);
                    curr = curr.children[1 - bit];
                } else {
                    curr = curr.children[bit];
                }
            }
            max = Math.max(max, currSum);
        }
        return max;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMaximum Product of Word Lengths
Next Question →Divide Two Integers