Algorithm
Step 1. Create a function “maximumXORValue()” that will accept the below parameters -
- “arr’’: The given array of integers
- “n”: Total number of elements in the given array
Step 2. First, initialize a variable “maxXOR” with zero.
Step 3. Create two nested for loops to find the XOR of all possible pairs and keep updating “maxXOR” variable with the maximum of XOR value obtained while running the loops.
Step 4. Return the “maxXOR” obtained after the completion of the running of the loops.
.
C++ code
#include <bits/stdc++.h>
using namespace std;
int maximumXORValue(int arr[], int n)
{
// Initialize a variable for storing the maximum XOR value
int maxXOR = 0;
// Calculating XOR of each pair
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
// Updating maxXOR with the maximum XOR value
maxXOR = max(maxXOR, arr[i] ^ arr[j]);
}
}
return maxXOR;
}
int main()
{
int n=6;
int arr[6] = { 25, 10, 2, 8, 5, 3 };
cout <<"The maximum xor value is: "<< maximumXORValue(arr, n) << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Output:
The maximum xor value is: 28
You can also try this code with Online C++ Compiler
Algorithm Complexity
Time Complexity: O(N ^ 2)
In the algorithm, two nested loops are used. So, the overall time complexity is O(N ^ 2), where ‘N’ is the number of elements in the given array.
Space Complexity: O(1)
As we have used constant space, so space complexity is O(1)
Efficient Approach
We can improve the time complexity by using a “trie” data structure. We can insert the binary representations of each of the numbers of the given array in the trie. We know that the XOR of two different bits is 1, and the two same bits are 0. So, to get the maximum XOR value, iterate through all the binary representations, and if the current bit is 0, find the path in the trie having value '1' and if the current bit is '1', then find the path having the value '0'.
Algorithm
Step 1: Create a Class ‘node’ for creating the trie data structure.
Step 2: Create a function “maximumXORValue()” which takes two parameters - the given array and its size and returns the maximum XOR value among the XOR values of all possible pairs in the array.
Step 3: Inside the function, first insert all the elements of the array in the trie. Create a helper function “insertElement()” for inserting an element into the trie.
Step 4: “insertElement()” function will take input an integer “currElement’’ and root node and will insert the “currElement” into the trie. While inserting the element into the trie, if the current bit is 0, then a node will be created to the left of the current node, else a node will be created to the right of the current node.
Step 5: Now, iterate through each element of the array, calculate the current XOR for each element, and update the maxXOR.
Step 6. Finally, return the “maxXOR” variable.
C++ Code
#include <bits/stdc++.h>
using namespace std;
// Defining the Class for creating Trie
class node {
public:
node* left;
node* right;
};
void insertElement(int x, node* root)
{
// Store the root
node* currNode = root;
for (int i = 30; i >= 0; i--)
{
// Find the i-th bit
int currBit = 1 & (x >> i);
// If the current bit is 0, create a node in the left
if (currBit == 0)
{
// If currNode->left is NULL
if (!currNode->left) currNode->left = new node();
// Update currNode to currNode->left
currNode = currNode->left;
}
// Else create a node in the right
else {
// If currNode->right is NULL
if (!currNode->right) currNode->right = new node();
// Update currNode to currNode->right
currNode = currNode->right;
}
}
}
int maximumXORValue(int arr[], int n)
{
// root Node of Trie
node* root = new node();
// Insert each element of the array in trie
for (int i = 0; i < n; i++)
{
insertElement(arr[i], root);
}
// Variable to store the maximum XOR value
int maxXOR = 0;
// Iterate through each element of the array
for (int i = 0; i < n; i++)
{
// Variable to store the XOR with current element of the array
int curr_xor = 0;
int M = pow(2, 30);
node* curr = root;
for (int j = 30; j >= 0; j--) {
// Finding ith bit
int val = (arr[i] >> j) & 1;
// if the bit is 0, then we have to go to the path with value 1, i.e. to the right child
if (val == 0)
{
// If right node exists, update the current XOR value
if (curr->right) {
curr_xor += M;
curr = curr->right;
}
else {
curr = curr->left;
}
}
// Else we have to go to the path with value 0, i.e. to the left child
else
{
// Check if left node exists, update the currentXOR
if (curr->left) {
curr_xor += M;
curr = curr->left;
}
else {
curr = curr->right;
}
}
// Update M to M/2 for next set bit
M /= 2;
}
// Update the maximum XOR
maxXOR = max(maxXOR, curr_xor);
}
// Return the maximum XOR found
return maxXOR;
}
int main()
{
// Given array arr[]
int arr[] = { 25, 10, 2, 8, 5, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout <<"The maxmum xor value is: "<< maximumXORValue(arr, n) << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Output:
The maximum xor value is: 28
Time Complexity: O(32 * N)
In the algorithm, a “for” loop is created to iterate through all the elements of the array, and for each element, another “for” loop is created to traverse through all the 32 bits of that element. So, the overall time complexity is O(32 * N), where ‘N’ is the number of elements in the given array.
Space Complexity: O(32 * N)
A trie is used for storing the binary representations of each element of the array, and there are 32 bits in each element. So, the space complexity is O(32 * N), where ‘N’ is the number of elements in the array.
Frequently asked questions
How to solve this question efficiently?
In the brute force approach, we have seen that how this problem can be solved in O(N ^ 2) time complexity by checking the XOR value for each possible pair of elements. But if we will use the properties of bitwise XOR, we can improve the time complexity and so we have used trie data structure for storing the binary representation of each element of the array. By using a trie data structure, we can efficiently store the binary representations and traverse each bit of an element according to our choice. This way the time complexity is reduced to O(N ^ 2).
What is a trie?
A trie data structure is a special type of search tree used for locating specific keys from within a set. In trie, the search complexity can be reduced to O(length of the key).
What is the time complexity of insertion and deletion in a trie?
The time complexity of a Trie data structure for insertion/deletion/search operation is O(n), where n is key length.
Conclusion
In this article, we discussed what the “Maximum XOR value pair” problem is, a brute force approach, and an efficient way to solve this problem programmatically, and discussed the time and space complexities. If you want to practice similar problems, then you can visit Coding Ninjas Studio.
Check out this problem - XOR Queries On Tree
If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.
34+ registered 
