Maximum XOR of Two Numbers in an Array

Master this topic with zero to advance depth.

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)$ in the array and calculate their XOR. Keep track of the maximum XOR found. Simple but $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 $X$ , we want to find a number $Y$ such that $X \oplus Y$ is maximized. At each bit $i$ of $X$ , if the $i$ -th bit is $b$ , we prioritize moving to a child representing $1-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;
    }
}

← Previous QuestionWord Squares

Next Question →Camelcase Matching

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.