Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Maximum XOR of Two Numbers in an Array

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<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;
    }
}
← Previous QuestionMaximum Product of Word Lengths
Next Question →Divide Two Integers