Trie Based Approach in C++


#1
struct Node
{
    Node *next[2];
    
    Node()
    {
        next[0]=NULL;
        next[1]=NULL;
    }
};
void insert(int A,Node* root)
{
    Node* temp = root;
    for(int i=31;i>=0;i--)
    {
        int bit = A>>i & 1;
        if(temp->next[bit] == NULL)
            temp->next[bit] = new Node();
        temp = temp->next[bit];
    }
    return;
}
int findxor(vector<int> &B,Node* root)
{
    Node* temp;
    int finalMax=0;
    for(int i=0;i<B.size();i++)
    {   temp = root;
        int currResult=0;
        for(int j=31;j>=0;j--)
        {
            int oppBit = ((B[i]>>j) & 1) ? 0 : 1; // If bit is 1 then oppBit (opposite bit) is 0 and vice-versa
            if(temp->next[oppBit]!=NULL) 
            {
                currResult = currResult<<1;
                currResult = currResult|1;
                temp = temp->next[oppBit];
            }
            else
            {
                currResult = currResult<<1;
                currResult = currResult|0; // This is not neccessary to write
                temp = temp->next[oppBit?0:1]; // Opposite Bit is not present so go to other bit
            }
        }
        if(currResult>finalMax)
            finalMax=currResult;
    }
    return finalMax;
}
int Solution::solve(vector<int> &A, vector<int> &B) {
    
    Node* root = new Node(); // Creating root node for trie
    for(int i=0;i<A.size();i++) // Binary representation of each element of array A is inserted in to Trie
        insert(A[i],root);
    int ans = findxor(B,root); // For Binary representation of each element of array B is compared in Trie
    return ans;
}