Advertisement
Maximum XOR of two numbers in an array
JavaView on GFG
Maximum XOR of two numbers in an array.java
Java
class Solution {
public int maxXor(int[] arr) {
TrieNode root = new TrieNode();
int maxResult = 0;
for (int num : arr)
insert(root, num);
for (int num : arr)
maxResult = Math.max(maxResult, findMaxXor(root, num));
return maxResult;
}
private void insert(TrieNode root, int num) {
TrieNode node = root;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[bit] == null)
node.children[bit] = new TrieNode();
node = node.children[bit];
}
}
private int findMaxXor(TrieNode root, int num) {
TrieNode node = root;
int maxXor = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
int oppositeBit = bit ^ 1;
if (node.children[oppositeBit] != null) {
maxXor |= (1 << i);
node = node.children[oppositeBit];
} else
node = node.children[bit];
}
return maxXor;
}
}
class TrieNode {
TrieNode[] children = new TrieNode[2];
}Advertisement
Was this solution helpful?