Given array nums, find maximum XOR of any two elements. Use a binary Trie for O(N) solution.
Input: [3,10,5,25,2,8] → Output: 28 (5 XOR 25)Input: [0,0] → Output: 0
Insert all numbers into a binary Trie. For each number, greedily try to go the opposite bit path to maximize XOR.
- For each num, insert 32-bit representation into Trie (MSB first).
- For each num, query Trie: at each bit, prefer going to opposite bit.
- XOR accumulates the best bits.
class Solution {
int[][] trie = new int[32 * 30001][2];
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, 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)