Maximum XOR of Two Numbers in an Array
Problem Description
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 * 105
- 0 <= nums[i] <= 231 - 1
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
For the brute force method, we consider each possible pair of numbers in the array and calculate their XOR. The XOR operation will give us a number with bits set where the bits differ between the two numbers. Our task is to find the two numbers that maximize this XOR. This approach checks all pairs and picks the one with the maximum XOR value.
Steps:
- Initialize a variable
maxXORto zero. - For every pair of numbers
(A[i], A[j])in the array, compute the XORA[i] ^ A[j]. - Update
maxXORif the computed XOR is greater thanmaxXOR. - Return
maxXOR.
Code:
- Time Complexity: O(n^2) - We iterate over all possible pairs in the array.
- Space Complexity: O(1) - No additional space is used except for a few variables.
2. Optimal Approach Using Trie
Intuition:
The key idea is to use a Trie (prefix tree) to efficiently find two numbers in the array that can form the maximum XOR result. By inserting all numbers in the Trie and using bit manipulation, we can find pairs leading to maximum XOR efficiently. This relies on the fact that XOR tends to maximize when we have opposing bits (i.e., one bit is 0, the other is 1).
Steps:
- Define a Trie structure with only two children for each node, representing a bit of
0or1. - Insert each number in the array into the Trie.
- As each number is inserted, simultaneously calculate the maximum XOR for that number with the previously inserted numbers in the Trie.
- Return the highest XOR obtained.
Code:
- Time Complexity: O(n * 32) - Each number is pushed into the Trie in O(32) time complexity, equivalent to the number of bits in an integer, and we process each number.
- Space Complexity: O(n * 32) - Space used in the Trie for storing all n numbers, each represented by a sequence of 32 bits.