281. Best XOR Pair
A signal-mixing board takes two input channels at a time and outputs the bitwise XOR of their readings. You are given the readings of all channels as the array nums and may choose any two different positions i != j (two positions may hold equal values, but you cannot pair a position with itself).
Return the largest XOR value that any such pair can produce. If every reading is identical the answer is 0. There are at least two channels, and all readings are non-negative integers below 2^30.
Trying every pair takes quadratic time, which is far slower than necessary for 4000 readings. Use the binary structure of the numbers to solve the problem in O(30 n) time.
Example 1
- Input:
- nums = [44,9,1000,531,70]
- Output:
- 993
- Explanation:
The best pair of readings XORs to 993.
Example 2
- Input:
- nums = [17,17,17]
- Output:
- 0
- Explanation:
The best pair of readings XORs to 0.
Example 3
- Input:
- nums = [262144,3]
- Output:
- 262147
- Explanation:
The best pair of readings XORs to 262147.
Constraints
2 ≤ nums.length ≤ 4000
0 ≤ nums[i] < 230
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(30 n)
- Space
- O(n)