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 - 1This approach involves iterating over all possible pairs of numbers in the array and calculating their XOR. We keep track of the maximum XOR value encountered during these iterations.
Though straightforward, this method is not efficient for large arrays, as it involves checking each pair of numbers.
The function findMaximumXOR takes an integer array and its size as arguments. It iterates over all pairs of elements in the array, calculating the XOR for each pair and updating the maximum XOR found so far. Finally, it returns the maximum XOR value.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), where n is the number of elements in the array, because it checks every pair.
Space Complexity: O(1), as it uses only a constant amount of space.
This approach makes use of a Trie data structure to efficiently maximize the XOR computation. By examining the binary representation of numbers, we can leverage the Trie to only explore branches that potentially maximize the XOR result.
The Trie helps in finding complementary patterns (bits) efficiently by using bit manipulation and path traversal.
This solution constructs a Trie to store the binary representation of each number. As each number is inserted into the Trie, we simultaneously seek to maximize the XOR by traversing potentially complementing paths (opposite bits in Trie nodes).
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * W), where n is the number of elements and W is the number of bits in the maximum number.
Space Complexity: O(n * W), for storing the Trie.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the number of elements in the array, because it checks every pair. |
| Trie-Based Approach | Time Complexity: O(n * W), where n is the number of elements and W is the number of bits in the maximum number. |
L6. Maximum XOR of Two Numbers in an Array | C++ | Java • take U forward • 93,161 views views
Watch 9 more video solutions →Practice Maximum XOR of Two Numbers in an Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor