# Minimum and Maximum Xor Value Pair

## 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. ## 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] = {123151150346410};
int mxXor = INT_MIN;
int mnXor = INT_MAX;
for (int i = 0i < ni++)
{
for (int j = i + 1j < nj++)
{
mxXor = max(mxXorarr[i] ^ arr[j]);
mnXor = min(mnXorarr[i] ^ arr[j]);
}
}
cout << “Max Xor pair possible “ << mxXor << endl;
cout << “Min Xor pair possible “ << mnXor << endl;
return 0;
}

### Output:

`Max Xor pair possible 61Min 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))) ### C++ Code

#include <bits/stdc++.h>
using namespace std;
class trieNode
{
public:
trieNode *zero;
trieNode *one;
trieNode()
{
zero = one = NULL;
}
};
{
for (int i = 30i >= 0i–)
{
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 *headint arr[], int n)
{
int mxXor = INT_MIN;
for (int i = 0i < ni++)
{
int val = arr[i];
int xr = 0;
for (int j = 30j >= 0j–)
{
/*
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(2j);
temp = temp->one;
}
else
{
temp = temp->zero;
}
}
else
{
if (temp->zero != NULL)
{
xr += pow(2j);
temp = temp->zero;
}
else
{
temp = temp->one;
}
}
}
mxXor = max(mxXorxr);
}
return mxXor;
}
{
int xr = 0;
for (int j = 30j >= 0j–)
{
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(2j);
temp = temp->one;
}
}
else
{
if (temp->one != NULL)
{
temp = temp->one;
}
else
{
xr += pow(2j);
temp = temp->zero;
}
}
}

return xr;
}

int main()
{
int n = 10;
int arr[n] = {123151150346410};

int mxXor = arr;
int mnXor = arr;
for (int i = 1i < ni++)
{
/*
The minimum is calculated every time as we don’t want
arr[i] to be checked with itself in the trie
*/
`Max Xor pair possible 61Min Xor pair possible 1`