# easy understanding C++ program and clear explanation

• ``````struct node{
bool val;
node *left,*right;
node(){
left=NULL;
right=NULL;
}
};
//this is the function to inset number to a trie
//the left child represent "1",right child represents "0"
void insert(node *root,int num,int d){
if(d==0) return;
int flag=num&d;
if(flag==d){//if we meet "1",then go right
if(root->right==NULL) root->right=new node;
root=root->right;
insert(root,num,d/2);
}else{//if we meet "0",then go left
if(root->left==NULL) root->left=new node;
root=root->left;
insert(root,num,d/2);
}
}

//find the other number that make the max XOR result
//It is just the opposite way of inserting,cause we want to find the max result of XOR
void compare(node *root,int num,int d,vector<int> &s){
if(d==0) return;
int flag=num&d;
if(flag==d){
//if we meet "1", we consider left child first,if the node has left child,it means we got a "1" bit in result and go left.
//if the node doesn't have left child ,we got a "0" bit in result and go right
if(root->left!=NULL){
s.push_back(1);
root=root->left;
}else if(root->right!=NULL){
s.push_back(0);
root=root->right;
}
compare(root,num,d/2,s);
}else{//just oppositely
if(root->right!=NULL){
s.push_back(1);
root=root->right;
}else if(root->left!=NULL){
s.push_back(0);
root=root->left;
}
compare(root,num,d/2,s);
}
}

``````
``````int findMaximumXOR(vector<int>& nums) {
//max_nums is the max number among nums
int max_nums=0;
for(int i=0;i<nums.size();i++){
if(nums[i]>max_nums) max_nums=nums[i];
}
//find the first "1" in max_nums(from left to right) and d represents that number
long long dd=1;
while((double)max_nums/dd>=1){
dd*=2;
}
int d=dd/2;
node *root=new node;
//create a trie for all the numbers
for(int i=0;i<nums.size();i++){
insert(root,nums[i],d);
}
int max=0;
//for each number in trie, we find the other number that make the max XOR result
for(int i=0;i<nums.size();i++){
vector<int> s;//store every bit of the max XOR result
int max_temp=0;
compare(root,nums[i],d,s);//to find the other number that make the max XOR result
for(int i=0;i<s.size();i++){//change the max result to decimal
max_temp=max_temp+pow(2.0,(s.size()-i-1)*1.0)*s[i];
}
if(max_temp>max) max=max_temp;
}
return max;
}
``````

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