Maximum XOR of Two Numbers in an Array
MedPrompt
Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.
Example 1:
Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.Example 2:
Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127
Constraints:
1 <= nums.length <= 2 * 1050 <= nums[i] <= 231 - 1
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to check every possible pair of numbers in the array. We can use two nested loops to iterate through all pairs (i, j), calculate nums[i] XOR nums[j], and keep track of the maximum value found.
Algorithm
- Initialize a variable
maxResultto 0. - Use two nested loops to iterate through all possible pairs of numbers
(nums[i], nums[j])in the array. - For each pair, calculate their XOR value:
currentXOR = nums[i] ^ nums[j]. - Compare
currentXORwithmaxResultand updatemaxResultifcurrentXORis greater. - After checking all pairs,
maxResultwill hold the maximum XOR value.
Walkthrough
This method exhaustively checks every unique pair of elements in the input array nums. It maintains a variable, maxResult, initialized to zero. The outer loop iterates from the first element to the last, and the inner loop iterates from the current element of the outer loop to the last. This ensures that each pair is considered exactly once (including a number with itself, which results in an XOR of 0). For each pair, their bitwise XOR is computed. If this result is larger than the current maxResult, maxResult is updated. This process guarantees that we find the maximum possible XOR value among all pairs.
class Solution { public int findMaximumXOR(int[] nums) { int maxResult = 0; int n = nums.length; if (n < 2) { return 0; } for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { maxResult = Math.max(maxResult, nums[i] ^ nums[j]); } } return maxResult; }}Complexity
Time
O(N^2), where N is the number of elements in the array. This is because of the two nested loops, each iterating up to N times.
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space, making its space complexity constant.
Cons
Extremely inefficient for large inputs due to its quadratic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms for the given constraints.
A more optimized approach involves building the maximum XOR result bit by bit, from the most significant bit (MSB) to the least significant bit (LSB). We can greedily try to make each bit of the result a '1' and use a HashSet to efficiently check if this is possible.
Algorithm
- Initialize
maxResult = 0andmask = 0. - Iterate from the most significant bit (MSB), say bit 31, down to the least significant bit (LSB), bit 0.
- In each iteration
i, update themaskto include the current bit:mask = mask | (1 << i). - Create a
HashSetto store the prefixes of all numbers innums. The prefix is calculated bynum & mask. - Greedily assume the
i-th bit of the final answer can be 1. Let this potential answer begreedyTry = maxResult | (1 << i). - To check if this is possible, we need to find if there are two numbers
aandbinnumssuch that their prefixes(a & mask) ^ (b & mask) == greedyTry. This is equivalent to checking if for any prefixpin our set,p ^ greedyTryalso exists in the set. - If such a pair of prefixes is found, it means our greedy assumption was correct. We update
maxResult = greedyTryand proceed to the next bit. - If not, the
i-th bit of the result must be 0, so we leavemaxResultas is. - After iterating through all bits,
maxResultwill hold the answer.
Walkthrough
This approach leverages the properties of XOR. We want to maximize the result, so we should try to make the most significant bits '1' whenever possible. We iterate from bit 31 down to 0. For each bit i, we determine if it's possible to have a '1' at this position in the final answer, given the choices we've made for the higher bits.
Let's say maxResult stores the result built so far. We test if we can form a new result temp = maxResult | (1 << i). This temp would be a valid prefix for our answer if there exist two numbers a and b in the input array such that a ^ b = temp. This is equivalent to a ^ temp = b.
To check this efficiently, we first compute the prefixes of all numbers in nums using a mask that covers bits from 31 down to i. We store these prefixes in a HashSet. Then, for each prefix in the set, we check if prefix ^ temp also exists in the set. If we find such a pair, we know that a '1' is achievable at bit i, so we update maxResult = temp. Otherwise, we move to the next bit, leaving the i-th bit of maxResult as '0'.
import java.util.HashSet;import java.util.Set; class Solution { public int findMaximumXOR(int[] nums) { int maxResult = 0; int mask = 0; // Integers are 32-bit, but since constraints are non-negative, we can start from bit 30 or 31. for (int i = 31; i >= 0; i--) { // The mask grows to include more bits from the left. // e.g., 100...0 -> 110...0 -> 111...0 mask = mask | (1 << i); Set<Integer> prefixes = new HashSet<>(); for (int num : nums) { prefixes.add(num & mask); } // Greedily try to set the i-th bit of the result to 1. int greedyTry = maxResult | (1 << i); for (int prefix : prefixes) { if (prefixes.contains(prefix ^ greedyTry)) { // If for a prefix 'p', 'p ^ greedyTry' also exists, it means we found two numbers // whose prefixes XOR to our greedy target. So, this bit can be 1. maxResult = greedyTry; break; } } } return maxResult; }}Complexity
Time
O(N * L), where N is the number of elements and L is the number of bits in the integers (here, L is constant, ~32). The outer loop runs L times, and inside it, we iterate through N elements twice (once to build the set, once to check).
Space
O(N), where N is the number of elements in the array. This is for storing the prefixes in the `HashSet` in each iteration.
Trade-offs
Pros
Significantly more efficient than the brute-force approach, with linear time complexity.
Provides a good foundation for understanding the more advanced Trie-based solution.
Cons
The logic can be non-intuitive at first glance.
Uses O(N) extra space for the HashSet, which might be significant for very large N.
The most efficient and standard solution for this problem uses a Trie (Prefix Tree). By storing the binary representations of all numbers in a Trie, we can efficiently query for each number x to find the number y in the set that maximizes x ^ y.
Algorithm
- Trie Node Definition: Define a
TrieNodeclass with an array (or map) of two children, one for bit0and one for bit1. - Build the Trie:
- Create a root
TrieNode. - For each number in
nums, insert its 32-bit binary representation into the Trie. Traverse from the MSB (bit 31) to the LSB (bit 0), creating nodes as necessary.
- Create a root
- Find Maximum XOR:
- Initialize
maxResult = 0. - For each number
numinnumsagain:- Traverse the Trie from the root to find the number that gives the maximum XOR with
num. - For each bit of
num(from MSB to LSB), greedily look for the opposite bit in the Trie. - If the opposite bit's path exists, take it. This means the corresponding bit in the XOR result will be
1. - If it doesn't exist, you must take the path of the same bit. The corresponding bit in the XOR result will be
0. - Build the
currentMaxXORfornumbit by bit. - Update the global
maxResultwithMath.max(maxResult, currentMaxXOR).
- Traverse the Trie from the root to find the number that gives the maximum XOR with
- Initialize
- Return
maxResult.
Walkthrough
A Trie is a perfect data structure for this problem because it organizes numbers based on their bit prefixes. To maximize an XOR result, we want to find a pair of numbers whose bits differ as much as possible, especially at the most significant positions.
First, we build the Trie. We iterate through each number in the input array nums. For each number, we traverse its binary representation from the most significant bit (31) to the least significant (0) and insert it into the Trie. Each node in the Trie represents a bit, and its children point to the next bits (0 or 1).
After building the Trie, we iterate through nums a second time. For each number num, we traverse the Trie to find its ideal XOR partner. Starting from the MSB of num, we look for the opposite bit in the Trie. For example, if the current bit of num is 0, we try to find a path for 1 in the Trie. If we succeed, we know this bit position in our XOR result will be 1, and we move to that child node. If the path for the opposite bit doesn't exist, we have no choice but to follow the path for the same bit, which results in a 0 at this bit position in the XOR result. We do this for all 32 bits, constructing the maximum possible XOR for num. We keep track of the overall maximum found across all numbers.
class TrieNode { TrieNode[] children; public TrieNode() { children = new TrieNode[2]; // 0 and 1 }} class Solution { public int findMaximumXOR(int[] nums) { TrieNode root = new TrieNode(); // 1. Insert all numbers into the Trie. for (int num : nums) { 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]; } } int maxResult = 0; // 2. For each number, find the max XOR partner in the Trie. for (int num : nums) { TrieNode curr = root; int currentXOR = 0; for (int i = 31; i >= 0; i--) { int bit = (num >> i) & 1; int oppositeBit = 1 - bit; if (curr.children[oppositeBit] != null) { // We can maximize this bit to 1. currentXOR = (currentXOR << 1) | 1; curr = curr.children[oppositeBit]; } else { // We have to settle for 0 at this bit. currentXOR = (currentXOR << 1) | 0; curr = curr.children[bit]; } } maxResult = Math.max(maxResult, currentXOR); } return maxResult; }}Complexity
Time
O(N * L), where N is the number of elements and L is the number of bits in the integers (~32). Building the Trie takes O(N*L) and querying for all numbers also takes O(N*L). Since L is constant, the complexity is effectively linear, O(N).
Space
O(N * L), where N is the number of elements and L is the number of bits. In the worst case, each number creates a unique path of L nodes in the Trie.
Trade-offs
Pros
Optimal time complexity, linear in the number of elements.
It's a canonical and versatile technique for a wide range of bitwise problems.
Cons
Requires implementation of a custom Trie data structure.
Space complexity can be higher than the HashSet approach in the worst case, as it stores the entire prefix structure.
Solutions
Solution
class Trie { private Trie [] children = new Trie [ 2 ]; public Trie () { } public void insert ( int x ) { Trie node = this ; for ( int i = 30 ; i >= 0 ; -- i ) { int v = x >> i & 1 ; if ( node . children [ v ] == null ) { node . children [ v ] = new Trie (); } node = node . children [ v ]; } } public int search ( int x ) { Trie node = this ; int ans = 0 ; for ( int i = 30 ; i >= 0 ; -- i ) { int v = x >> i & 1 ; if ( node . children [ v ^ 1 ] != null ) { ans |= 1 << i ; node = node . children [ v ^ 1 ]; } else { node = node . children [ v ]; } } return ans ; } } class Solution { public int findMaximumXOR ( int [] nums ) { Trie trie = new Trie (); int ans = 0 ; for ( int x : nums ) { trie . insert ( x ); ans = Math . max ( ans , trie . search ( x )); } return ans ; } }class Trie { public: Trie * children [ 2 ]; Trie () : children { nullptr , nullptr } {} void insert ( int x ) { Trie * node = this ; for ( int i = 30 ; ~ i ; -- i ) { int v = x >> i & 1 ; if ( ! node -> children [ v ]) { node -> children [ v ] = new Trie (); } node = node -> children [ v ]; } } int search ( int x ) { Trie * node = this ; int ans = 0 ; for ( int i = 30 ; ~ i ; -- i ) { int v = x >> i & 1 ; if ( node -> children [ v ^ 1 ]) { ans |= 1 << i ; node = node -> children [ v ^ 1 ]; } else { node = node -> children [ v ]; } } return ans ; } }; class Solution { public: int findMaximumXOR ( vector < int >& nums ) { Trie * trie = new Trie (); int ans = 0 ; for ( int x : nums ) { trie -> insert ( x ); ans = max ( ans , trie -> search ( x )); } return ans ; } };class Trie : __slots__ = ( "children" ,) def __init__ ( self ): self . children : List [ Trie | None ] = [ None , None ] def insert ( self , x : int ): node = self for i in range ( 30 , - 1 , - 1 ): v = x >> i & 1 if node . children [ v ] is None : node . children [ v ] = Trie () node = node . children [ v ] def search ( self , x : int ) -> int : node = self ans = 0 for i in range ( 30 , - 1 , - 1 ): v = x >> i & 1 if node . children [ v ^ 1 ]: ans |= 1 << i node = node . children [ v ^ 1 ] else : node = node . children [ v ] return ans class Solution : def findMaximumXOR ( self , nums : List [ int ]) -> int : trie = Trie () for x in nums : trie . insert ( x ) return max ( trie . search ( x ) for x in nums )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.