# Maximum XOR using trie data structure with Java

To find the maximum xor between two numbers. The program finds the best number from the array so the xor between that number and the inputted number is maximum.

Using the brute force method Maximum Xor can be found between two numbers by using the bitwise xor operator. But if we are using the same array or a set of numbers to find maximum xor with another number our operation becomes costly.

In this tutorial, we will see how to construct a trie and find maximum xor using a trie.

eg: [1, 2, 5] is the array given and num = 2, the maximum xor is 5^2 = 7

1: construct trie of height 32 (int) for every integer the array using "insert(trie head, int num, int pos)"

2: then traverse the tree to get maximum xor using "find_max" function.

```import java.util.*;

public class Maximum_xor {
static class trie{		//class to store the number as a trie
trie left, right;
public trie(){
left = null;
right = null;
}
}

//inserting nodes in trie
static void insert(trie head, int num, int pos){
for(int i = pos; i>=0; i--){
//if i'th of num is 1 move right and create a new node if
//no right node is present
if( (num>>i & 1) == 1){
if(temp.right == null)
temp.right = new trie();
temp = temp.right;
}
//if i'th of num is 0 do the same by moving left
else{
if(temp.left == null)
temp.left = new trie();
temp = temp.left;
}
}
}

//pos is (maximum bit value -1) eg. for int pos = 31
static int find_max(trie head, int num, int pos){
int ret = 0;	//store result

for(int i = pos; i>=0; i--){
if((num>>i&1) == 1){

//if present binary value is 1 move
//left to get maximum
if(node.left != null){
node = node.left;
ret += Math.pow(2, i);
}
//no opposite value present so
//xor will give 0
else
node = node.right;
}
else{
if(node.right != null){
node = node.right;
ret += Math.pow(2, i);
}
else
node = node.left;
}
}
return ret;
}

public static void main(String args[]){
System.out.println("Enter array size: ");
int n;
Scanner s = new Scanner(System.in);
n = s.nextInt();
int[] arr = new int[n];

System.out.println("Enter array: ");
for(int i=0; i<n; i++){
arr[i] = s.nextInt();
insert(head, arr[i], 31); //int has 32 bits so pos is 31
}

int q;
System.out.println("Enter number for maximum xor: ");
q = s.nextInt();
System.out.println("Maximum xor " + find_max(head, q, 31));

}
}```

Output: 