# JAVA solution with trie and bit operation 94% O(n)

• ``````    /*we use the Trie to solve the problem
for example [10,20]
10:0000.... 1010
20:0000....0001 0010.
we use every one bit as a Node value;
then we use two point to analyse whether it should be insert and whether the int[] max should be validate*/
class TrieNode{
TrieNode[] next;
TrieNode(){
next = new TrieNode[2];
}
}

class Trie{
Set<Integer> set;
final int bit;
TrieNode root;
int[] max;
Trie(){
root = new TrieNode();
max = new int[31];
bit =(int)Math.pow(2, 30);
set = new HashSet<>();
}
//refresh max[] and insert the number
public void analyse(int num){
if (set.contains(num)) {
return;
}
if (set.isEmpty()) {
insertNode(num,root,bit);
return;
}
TrieNode p1 = root;//use the point analyse the insertion
TrieNode p2 = root;//use the point analyse the refresh
int index = 0;//the position of the arr[]
int tmp = bit;// the bit operation initial
while (index < max.length) {
int k =(num & tmp) == 0? 0:1;//get the bit val of ervery position
if (p2.next[1 - k] == null) {
if (p1.next[k] == null) {
p1.next[k] = new TrieNode();
}
if (max[index] == 1) {
insertNode(num,p1.next[k],tmp >> 1);
return;
}
p1 = p1.next[k];
p2 = p2.next[k];
}else {
if (p1.next[k] == null) {
p1.next[k] = new TrieNode();
}
if (max[index] == 0) {
max[index] = 1;
reFresh(max, index + 1, num, tmp>>1, p1.next[k],p2.next[1 - k]);
return;
}else {
p1 = p1.next[k];
p2 = p2.next[1 - k];
}
}
index ++;
tmp >>= 1;
}

}
//refresh the max[]
private void reFresh(int[] max, int i, int num, int tmp, TrieNode p1, TrieNode p2) {
while (i < max.length) {
int k =(num & tmp) == 0? 0:1;
if (p2.next[1 - k] != null) {
max[i] = 1;
p2 = p2.next[1 - k];
}else {
max[i] = 0;
p2 = p2.next[k];
}
if (p1.next[k] == null) {
p1.next[k] = new TrieNode();
}
p1 = p1.next[k];
i ++;
tmp >>= 1;
}
}
// insert the node
private void insertNode(int num, TrieNode p1, int tmp) {
while (tmp != 0) {
int k =(num & tmp) == 0? 0:1;
if (p1.next[k] == null){
p1.next[k] = new TrieNode();
}
p1 = p1.next[k];
tmp >>= 1;
}
}
public int getResult() {
int res = 0;
for (int i = 0; i < max.length; i ++) {
res += max[i] * Math.pow(2, 30 - i);
}
return res;
}
}

public int findMaximumXOR(int[] nums) {
Trie tree = new Trie();
for (int k : nums) {
tree.analyse(k);
}
return tree.getResult();
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.