Maximum XOR Pair

Find the maximum XOR of any two numbers in an array using bit manipulation.

bit-manipulation xor array algorithm

Given a non-empty list of non-negative integers `nums`, implement a function `max_xor_pair(nums)` that returns the maximum possible value of `nums[i] XOR nums[j]` for any two distinct indices `i` and `j`. The result is the integer value of that maximum XOR. For example, if `nums = [3, 10, 5, 25, 2, 8]`, the maximum XOR is `28` (from `5 XOR 25 = 28`). You must solve it efficiently using bit manipulation (an O(n * b) approach is expected, where b is the bit-length of the largest number). The order of indices does not matter, and you may use the same value from two different positions (if it appears twice), but you must use two distinct indices.

Write your solution in the `max_xor_pair` function.

Constraints

- `1 <= len(nums) <= 10^5`
- `0 <= nums[i] <= 2^31 - 1` (i.e., fits in a 32-bit unsigned integer)
- All numbers are non-negative integers.
- The expected time complexity is O(n * b), where b = max(1, bit_length of max(nums)). Space: O(n).

Example

>>> max_xor_pair([3, 10, 5, 25, 2, 8])
28
>>> max_xor_pair([0])
0
>>> max_xor_pair([1, 2, 3])
3
>>> max_xor_pair([8, 10, 2])
10

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about building the answer bit by bit from the most significant bit to the least significant bit.

For each prefix of numbers (masked to the bits you've considered so far), try to see if there exists a pair that can achieve the candidate answer using a set.

Remember that XOR pairs can be checked by seeing if for a candidate x, there exist a and b in the set such that a ^ b == x, which is equivalent to b = a ^ x.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.