Minimum and Maximum Xor Value Pair

November 6, 2021

Minimum and Maximum Xor Value Pair in C++

The problem asks us to find the minimum and maximum xor value possible from the elements provided we take only two elements. With this problem we cover how to apply trie in problems in which we have to do some binary operations. 

Here is a detailed explanation  and implementation in C++ for the problem.

problemDescription

Minimum and Maximum Xor Value Problem Description

We are given n integers and have to return the maximum and minimum xor value pair possible. We have to output the required values.

Example :

n = 3

The integer array is [1, 2, 3].

The output should be:

Max Xor pair possible 3
Min Xor pair possible 1

Explanation:

3 is obtained by bit wise xor of 1 and 2.

1 is obtained by bit wise xor of 2 and 3.

Minimum and Maximum Xor Value Solution Explanation

Naive Solution

The basic or naive approach is to use two nested loops and compute xor values for every pair possible and update minimum and & maximum xor value.

The time complexity of this approach is O(n^2).  Which will time out if n > 10^4.

Code for naive approach is implemented below.

C++ Code

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n = 10;
    int arr[n] = {1, 2, 3, 15, 11, 50, 34, 6, 4, 10};
    int mxXor = INT_MIN;
    int mnXor = INT_MAX;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            mxXor = max(mxXor, arr[i] ^ arr[j]);
            mnXor = min(mnXor, arr[i] ^ arr[j]);
        }
    }
    cout << “Max Xor pair possible “ << mxXor << endl;
    cout << “Min Xor pair possible “ << mnXor << endl;
    return 0;
}

Output:

Max Xor pair possible 61
Min Xor pair possible 1

Optimized Solution

The optimized solution uses trie. We create a trie with node structure which points to only two child nodes 0 bit and one bit. We add the numbers in binary format in the trie from maximum bit (Integer limit , varies according to the constraints) to minimum bit ( ie 0). Then we will calculate the minimum and maximum xor value pair using the trie.

The time complexity – O(nlog(max(arr value)))

Below image with help you visualize how trie is created.

Inserting Trie Visualization

C++ Code

#include <bits/stdc++.h>
using namespace std;
class trieNode
{
public:
    trieNode *zero;
    trieNode *one;
    trieNode()
    {
        zero = one = NULL;
    }
};
void insert(int n, trieNode *head)
{
    trieNode *temp = head;
    for (int i = 30; i >= 0; i–)
    {
        int bit = (n >> i) & 1;
        if (bit == 0)
        {
            if (temp->zero == NULL)
                temp->zero = new trieNode();
            temp = temp->zero;
        }
        else
        {
            if (temp->one == NULL)
                temp->one = new trieNode();
            temp = temp->one;
        }
    }
}
int getMaxXorPair(trieNode *head, int arr[], int n)
{
    int mxXor = INT_MIN;
    for (int i = 0; i < n; i++)
    {
        int val = arr[i];
        trieNode *temp = head;
        int xr = 0;
        for (int j = 30; j >= 0; j–)
        { 
            /*
                for maximum check the current bit and 
                try moving to opposite bit value
            */
            int bit = (val >> j) & 1;
            if (bit == 0)
            {
                if (temp->one != NULL)
                {
                    xr += pow(2, j);
                    temp = temp->one;
                }
                else
                {
                    temp = temp->zero;
                }
            }
            else
            {
                if (temp->zero != NULL)
                {
                    xr += pow(2, j);
                    temp = temp->zero;
                }
                else
                {
                    temp = temp->one;
                }
            }
        }
        mxXor = max(mxXor, xr);
    }
    return mxXor;
}
int getMinXorPair(trieNode *head, int val)
{
    trieNode *temp = head;
    int xr = 0;
    for (int j = 30; j >= 0; j–)
    {
        int bit = (val >> j) & 1;
        if (bit == 0)
        {
            /*
                for maximum check the current bit and 
                try moving to same bit value
            */
            if (temp->zero != NULL)
            {
                temp = temp->zero;
            }
            else
            {
                xr += pow(2, j);
                temp = temp->one;
            }
        }
        else
        {
            if (temp->one != NULL)
            {
                temp = temp->one;
            }
            else
            {
                xr += pow(2, j);
                temp = temp->zero;
            }
        }
    }

    return xr;
}

int main()
{
    trieNode *head = new trieNode();
    int n = 10;
    int arr[n] = {1, 2, 3, 15, 11, 50, 34, 6, 4, 10};

    int mxXor = arr[0];
    int mnXor = arr[0];
    insert(arr[0], head);
    for (int i = 1; i < n; i++)
    {
        /*
            The minimum is calculated every time as we don’t want 
            arr[i] to be checked with itself in the trie
        */
        mnXor = min(mnXor, getMinXorPair(head, arr[i]));
        insert(arr[i], head);
    }

    mxXor = getMaxXorPair(head, arr, n);
    cout << “Max Xor pair possible “ << mxXor << endl;
    cout << “Min Xor pair possible “ << mnXor << endl;
    return 0;
}

Output:

Max Xor pair possible 61
Min Xor pair possible 1