Maximum Xor between Two Arrays | Trie

Question

Given two integer vectors A and B, we have to pick one element from each vector such that their xor is maximum and we need to return this maximum xor value from the function int Solution::solve(vector &A, vector &B).

I found out that the code below is not passing all the test cases when I'm declaring and initializing the head pointer globally right beneath the class Trienode. Why is that?

Code

class Trienode
{
    public:
        Trienode* left;
        Trienode* right;

        Trienode()
        {
            left=0;
            right=0;
        }
};

// Trienode* head = new Trienode;


int Max_Xor_Pair(Trienode* head, vector<int> B)
{
    int n=B.size();
    int max_xor=INT_MIN;

    for(int i=0; i<n; i++)
    {
        int pair1 = B[i];
        int pair2 = 0;
        Trienode* curr=head;

        for(int j=31; j>=0; j--)
        {
            int bit = (pair1>>j)&1;

            if(bit)
            {
                if(curr->left)
                    curr=curr->left;
                else
                {
                    curr=curr->right;
                    pair2 += pow(2,j);
                }
                    
            }
            else
            {
                if(curr->right)
                {
                    curr=curr->right;
                    pair2 += pow(2,j);
                }
                else
                    curr=curr->left;
            }

        }

        int curr_xor = pair1 ^ pair2;
        max_xor = max(max_xor, curr_xor);
    }
    
    return max_xor;
}

void Insert(Trienode* head, int num)
{
    Trienode* curr=head;
    for(int i=31; i>=0; i--)
    {
        int x = num;
        int bit= (x>>i)&1;

        if(bit)
        {
            if(!curr->right)
            {
                Trienode* temp = new Trienode;
                curr->right=temp;
            }
            curr=curr->right;            
        }
        else
        {
            if(!curr->left)
            {
                Trienode* temp = new Trienode;
                curr->left=temp;
            }
            curr=curr->left;            
        }
    }
}


int Solution::solve(vector<int> &A, vector<int> &B) {

    Trienode* head = new Trienode;

    for(int x:A)
        Insert(head,x);

    return Max_Xor_Pair(head,B);
}

Sample Input

A : [ 15891, 6730, 24371, 15351, 15007, 31102, 24394, 3549, 19630, 12624, 24085, 19955, 18757, 11841, 4967, 7377, 13932, 26309, 16945, 32440, 24627, 11324, 5538, 21539, 16119, 2083, 22930, 16542, 4834, 31116, 4640, 29659, 22705, 9931, 13978, 2307, 31674, 22387, 5022, 28746, 26925, 19073, 6271, 5830, 26778, 15574, 5098, 16513, 23987, 13291, 9162 ]

B : [ 18637, 22356, 24768, 23656, 15575, 4032, 12053, 27351, 1151, 16942 ]

Answer 1

When head is a global variable, and you don't have this line in Solution::solve:

 Trienode* head = new Trienode;

...then head will retain its value after the first test case has finished, and so the second test case will not start with an empty tree. Each test case will add more nodes to the one tree. Of course this means that, except for the first test case, the tree rooted by head is not the intended tree.

To make the version with the global variable work, reset it in Solution::solve:

head->left = head->right = nullptr;

BTW, you should also initialise these members with nullptr (instead of 0) in your TrieNode constructor. This better reflects the intent.