Course4all

Maximum XOR of Two Numbers in an Array

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trie.

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 < n.

Visual Representation

Nums: [3, 10, 5, 25, 2, 8] Max XOR: 5 XOR 25 = 28 Binary Trie approach: 1. Insert all numbers as 32-bit binary strings into a Trie. 2. For each number X, find a path that maximizes XOR. 3. To maximize XOR, at each bit, try to go to the opposite bit (if curr is 0, try 1). If opposite exists, result |= (1 << bit).
Medium

Examples

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

Level I: Brute Force

Intuition

Check every pair of numbers (i,j)(i, j) in the array and calculate their XOR. Keep track of the maximum XOR found. Simple but O(N2)O(N^2).
⏱ O(N^2)💾 O(1)
java
class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++)
            for (int j = i; j < nums.length; j++) max = Math.max(max, nums[i] ^ nums[j]);
        return max;
    }
}
Approach 2

Level III: Binary Trie

Intuition

Represent each number as a 31-bit or 32-bit binary string. Insert all numbers into a Trie where each node has at most two children (0 and 1). For each number XX, we want to find a number YY such that X⊕YX \oplus Y is maximized. At each bit ii of XX, if the ii-th bit is bb, we prioritize moving to a child representing 1−b1-b in the Trie. This greedy choice at each bit ensures the maximum possible XOR value.
⏱ O(N * 31) = O(N).💾 O(N * 31).
java
class Solution {
    class Node { Node[] children = new Node[2]; }
    public int findMaximumXOR(int[] nums) {
        Node root = new Node();
        for (int n : nums) {
            Node curr = root;
            for (int i = 31; i >= 0; i--) {
                int bit = (n >> i) & 1;
                if (curr.children[bit] == null) curr.children[bit] = new Node();
                curr = curr.children[bit];
            }
        }
        int max = 0;
        for (int n : nums) {
            Node curr = root; int val = 0;
            for (int i = 31; i >= 0; i--) {
                int bit = (n >> i) & 1;
                if (curr.children[1 - bit] != null) { val |= (1 << i); curr = curr.children[1 - bit]; }
                else curr = curr.children[bit];
            }
            max = Math.max(max, val);
        }
        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 QuestionWord Squares
Next Question →Camelcase Matching