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.
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 ; } }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.