Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.
Input: [3,10,5,25,2,8] → Output: 28 (5 XOR 25)Input: [14,70,53,83,49,91,36,80,92,51,66,70] → Output: 127
Use a Trie built on the 32-bit representation of each number. For each number, traverse the Trie trying to go the opposite bit direction (to maximize XOR). Build the Trie on all numbers first.
- Build a binary Trie: for each number, insert all 32 bits (MSB first).
- For each number, traverse the Trie greedily: prefer the branch whose bit differs from current bit.
- XOR each chosen bit with the current bit and accumulate.
- Return the maximum XOR found.
class Solution {
private int[][] trie = new int[32 * 10001][2];
private int node = 1;
public int findMaximumXOR(int[] nums) {
for (int num : nums) insert(num);
int max = 0;
for (int num : nums) max = Math.max(max, query(num));
return max;
}
private void insert(int num) {
int cur = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (trie[cur][bit] == 0) trie[cur][bit] = node++;
cur = trie[cur][bit];
}
}
private int query(int num) {
int cur = 0, xor = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
int want = 1 - bit;
if (trie[cur][want] != 0) { xor |= (1 << i); cur = trie[cur][want]; }
else cur = trie[cur][bit];
}
return xor;
}
}
- Time Complexity: O(N * 32)
- Space Complexity: O(N * 32)