Maximum Xor

                        Solution in C++ :

In   C++  :








#include <bits/stdc++.h>
using namespace std;

int p;
struct node
{
    int val;
    node *child[2];
};

void insert(node *trie, int x, int ind)
{   
    if(ind < 0) {
        return;
    }
    int k=(x>>ind)&1;

    if(!trie->child[k]) {
        trie->child[k]=new node;
    }
    insert(trie->child[k], x, ind-1);
}

void find(node *trie, int x, int ind)
{   
    if(ind<0) {
        return;
    }

    int k=(x>>ind)&1;
    k^=1;

    if(!trie->child[k]) {
        k^=1;
    }
    p=p<<1|k;
    find(trie->child[k], x, ind-1);
}

int main()
{
    int n,i,x;
    cin>>n;

    int a[n];
    for(i=0;i<n;++i) {
        cin>>a[i];
    }

    node *trie = new node;
    for(i=0;i<n;++i) {
        // max 32 bits
        insert(trie,a[i],31);
    }

    int t;
    cin>>t;
    while(t--) {
        cin>>x;
        p=0;
        find(trie,x,31);
        cout<<(p^x)<<endl;
    }

    return 0;
}
                    

                        Solution in Java :

In   Java   :









static final int INT_SIZE = 32; 

// A Trie Node 
static class TrieNode 
{ 
    int value;  // Only used in leaf nodes 
    TrieNode[] arr =  new TrieNode[2]; 
    public TrieNode() { 
        value = 0; 
        arr[0] = null; 
        arr[1] = null; 
    } 

    public String toString(){
        return "{ value: "+this.value+" "+ arr.toString()+"}";
    }
} 
static TrieNode root;

static void insert(int pre_xor) 
{ 
    TrieNode temp = root; 

    for (int i=INT_SIZE-1; i>=0; i--) 
    { 
        int val = (pre_xor & (1<<i)) >=1 ? 1 : 0; 

        if (temp.arr[val] == null) 
            temp.arr[val] = new TrieNode(); 

        temp = temp.arr[val]; 
    } 
    temp.value = pre_xor; 
} 

static int query(int pre_xor) 
{ 
    TrieNode temp = root; 
    for (int i=INT_SIZE-1; i>=0; i--) 
    { 
        int val = (pre_xor & (1<<i)) >= 1 ? 1 : 0; 

        if (temp.arr[val] != null) 
            temp = temp.arr[val]; 

        else if (temp.arr[1-val] != null) 
            temp = temp.arr[1-val];
    } 
    return (~pre_xor)^(temp.value); 
}
// Complete the maxXor function below.
static int[] maxXor(int[] arr, int[] queries) {
    int[] result = new int[queries.length];

    root = new TrieNode(); 
    insert(0);
    int pre_xor =0; 
    int max = Integer.MIN_VALUE;
    for (int i=0; i<arr.length; i++) 
    {  
        insert(arr[i]);
    }  

    for(int j=0; j<queries.length;j++){
        pre_xor = ~queries[j];  
        //max= Math.max(max, query(pre_xor));
        result[j]=query(pre_xor);
    }
    return result;
}
                    

                        Solution in Python : 
                            
In   Python3  :







def maxXor(arr, queries):
    ans = []
    trie = {}
    k = len(bin(max(arr+queries))) - 2 
    for number in ['{:b}'.format(x).zfill(k) for x in arr]:
        node = trie
        for char in number:
            node = node.setdefault(char, {})
    for n in queries:
        node = trie
        s = ''
        for char in'{:b}'.format(n).zfill(k) :
            tmp = str(int(char) ^ 1) 
            tmp = tmp if tmp in node else char 
            s += tmp 
            node = node[tmp]
        ans.append(int(s, 2) ^ n) 
    return ans