Advanced Data Structures: Implementing Tries in C++ and Java/

...

/

Solution Review: Minimum XOR

Solution Review: Minimum XOR

See the solution to the minimum XOR problem challenge.

We'll cover the following...

Solution

C++
Java
#include <iostream>

#include <vector>

#include <limits.h>

using namespace std;



// Defining the max limit on number of bits

#define MAX_BIT_COUNT 32



class TrieNode

{

    public:

        // the integer value stored at the leaf node

        int value;

        // each trie node can have only two children (0 and 1)

        TrieNode *children[2];

};



class Trie

{

    public:

        TrieNode * root;



        Trie()

        {

            root = new TrieNode();

        }

    

       	// utility function insert new key in trie

        void insert(int num)

        {

           	// initialize current node to root

            TrieNode *curr = root;

    

           	// start from the most significant bit, insert all

           	// bit of integer into trie

            for (int i = MAX_BIT_COUNT - 1; i >= 0; i--)

            {

               	// find current bit in given prefix

                bool currentBit = (num &(1 << i));

    

               	// Create a new node in the trie

                if (curr->children[currentBit] == NULL)

                    curr->children[currentBit] = new TrieNode();

    

                curr = curr->children[currentBit];

            }

    

           	// store the integer value at the leaf node

            curr->value = num;

        }

    

        int findMinXOR(int num)

        {

           	// initialize current node to root

            TrieNode *curr = root;

    

            for (int i = MAX_BIT_COUNT - 1; i >= 0; i--)

            {

               	// find current bit in given prefix

                bool currentBit = (num &(1 << i));

               	// check for prefix that has same bit

                if (curr->children[currentBit] != NULL)

                    curr = curr->children[currentBit];

               	// check for opposite bit, if same bit not found

                else if (curr->children[1 - currentBit] != NULL)

                    curr = curr->children[1 - currentBit];

            }

    

           	// return xor value of minimum bit difference value

           	// so we get minimum xor value

            return num ^ curr->value;

        }

};



// Returns minimum xor value of pair in arr[0..n-1]

int minimumXOR(vector<int> nums)

{

    int n = nums.size();

    

    // Initialize result

    int minXOR = INT_MAX;	

    

    // Initialize a trie

    Trie *trie = new Trie();



   	// insert the first integer from the list into trie

    trie->insert(nums[0]);



   	// Iterate through all integers and find minimum XOR for every element

    for (int i = 1; i < n; i++)

    {

       	// Find minimum XOR value of current element with

       	// previous elements inserted in Trie

        minXOR = min(minXOR, trie->findMinXOR(nums[i]));



       	// insert current integers value into trie

        trie->insert(nums[i]);

    }



    return minXOR;

}
Solution for problem challenge in C++

Intuition

Since bitwise tries are used to store binary prefixes efficiently, we can use bitwise tries to solve this problem. We'll convert all the array numbers into their binary forms and insert them into the trie, where each node will represent a bit of the number.

Algorithm

The summary of the algorithm is given below.

Step 1: Insertion in a trie

Convert all the integers from decimal to binary form and insert the bits into the trie. This implies that every trie node can have only two possible children, 0 and 1. Finally, add an integer parameter value to the definition of the trie node to store the final integer value in the leaf node.

C++
Java
// Definition of TrieNode
class TrieNode
{
    public:
       	// the integer value stored at the leaf node
        int value;
       	// each trie node can have only two children (0 and 1)
        TrieNode *children[2];
};
Definition of a trie node in a bitwise trie in C++

Step 2: Finding the minimum XOR

The minimum value for the XOR of any two bits is 1. This is only achievable if the two bits involved are the opposite value of each other—that is, XORing 0 with 0 or 1 with 1 would result in a minimum value of 0.

Once we have a bitwise trie of numbers, we can calculate the minimum XOR with another number by traversing the trie downward, with the current number in binary form, and at each step, choosing the child node that will yield the minimum XOR value. 

To minimize XOR, the strategy is to choose the same bit at each step whenever possible. If the current bit value of a number is 1, we'll try to choose the 1 children of the current node in the trie and vice versa. This will give us the minimum value of XOR. 

Add the binary numbers into the trie one by one, creating a bitwise trie, and compute the minimum XOR of a number with all the previously inserted binaries. Try choosing the same bit at every step to minimize the XOR value. Update minimum XOR at each step. Return the value of minXOR as the answer.

Visualization

The following picture explains the construction of a bitwise trie and the steps to find the minimum XOR for an integer with other integers in the trie.

Complexity analysis

Variables

  • Number of integers in list =NN.

  • The average length of the binary representation of the integers = WW ...