Naive Approach: A Simple Solution is to generate all pairs of the given array and compute the XOR of the pairs. Finally, return the maximum XOR value. This solution takes time. Below is the implementation of the above approach:
C++
// C++ implementation
#include <bits/stdc++.h>
usingnamespacestd;
// Function to return the
// maximum xor
intmax_xor(intarr[], intn)
{
intmaxXor = 0;
// Calculating xor of each pair
for(inti = 0; i < n; i++) {
for(intj = i + 1; j < n; j++) {
maxXor = max(maxXor,
arr[i] ^ arr[j]);
}
}
returnmaxXor;
}
// Driver Code
intmain()
{
intarr[] = { 25, 10, 2, 8, 5, 3 };
intn = sizeof(arr) / sizeof(arr[0]);
cout << max_xor(arr, n) << endl;
return0;
}
Java
// Java implementation of the approach
classGFG
{
// Function to return the
// maximum xor
staticintmax_xor(intarr[], intn)
{
intmaxXor = 0;
// Calculating xor of each pair
for(inti = 0; i < n; i++)
{
for(intj = i + 1; j < n; j++)
{
maxXor = Math.max(maxXor,
arr[i] ^ arr[j]);
}
}
returnmaxXor;
}
// Driver Code
publicstaticvoidmain(String[] args)
{
intarr[] = {25, 10, 2, 8, 5, 3};
intn = arr.length;
System.out.println(max_xor(arr, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation
# Function to return the
# maximum xor
defmax_xor(arr, n):
maxXor =0;
# Calculating xor of each pair
fori inrange(n):
forj inrange(i +1, n):
maxXor =max(maxXor,\
arr[i] ^ arr[j]);
returnmaxXor;
# Driver Code
if__name__ =='__main__':
arr =[ 25, 10, 2, 8, 5, 3];
n =len(arr);
print(max_xor(arr, n));
# This code is contributed by 29AjayKumar
C#
// C# implementation of the approach
usingSystem;
classGFG
{
// Function to return the
// maximum xor
staticintmax_xor(int[]arr, intn)
{
intmaxXor = 0;
// Calculating xor of each pair
for(inti = 0; i < n; i++)
{
for(intj = i + 1; j < n; j++)
{
maxXor = Math.Max(maxXor,
arr[i] ^ arr[j]);
}
}
returnmaxXor;
}
// Driver Code
publicstaticvoidMain()
{
int[]arr = {25, 10, 2, 8, 5, 3};
intn = arr.Length;
Console.WriteLine(max_xor(arr, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation
// Function to return the
// maximum xor
functionmax_xor(arr, n)
{
let maxXor = 0;
// Calculating xor of each pair
for(let i = 0; i < n; i++) {
for(let j = i + 1; j < n; j++) {
maxXor = Math.max(maxXor,
arr[i] ^ arr[j]);
}
}
returnmaxXor;
}
// Driver Code
let arr = [ 25, 10, 2, 8, 5, 3 ];
let n = arr.length;
document.write(max_xor(arr, n));
</script>
Output
28
Time Complexity: O(N^{2}) , where N is the size of the array Auxiliary Space: O(1) Efficient Approach: The approach is similar to this article where the task is to find the maximum AND value pair. So the idea is to change the problem statement from finding the maximum xor of two numbers in an array to -> find two numbers in an array, such that xor of which equals to a number X. In this case, X will be the maximum number we want to achieve till i-th bit. To find the largest value of an XOR operation, the value of xor should have every bit to be a set bit i.e 1. In a 32-bit number, the goal is to get the most 1 set starting left to right. To evaluate each bit, there is a mask needed for that bit. A mask defines which bit should be present in the answer and which bit is not. Here we will use a mask to keep the prefix for every number ( means by taking the ans with the mask how many bits are remaining from the number ) in the input till the i-th bit then with the list of possible numbers in our set, after inserting the number we will evaluate if we can update the max for that bit position to be 1. Below is the implementation of the above approach:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
usingnamespacestd;
// Function to return the
// maximum xor
intmax_xor(intarr[], intn)
{
intmaxx = 0, mask = 0;
set<int> se;
for(inti = 30; i >= 0; i--) {
// set the i'th bit in mask
// like 100000, 110000, 111000..
mask |= (1 << i);
for(inti = 0; i < n; ++i) {
// Just keep the prefix till
// i'th bit neglecting all
// the bit's after i'th bit
se.insert(arr[i] & mask);
}
intnewMaxx = maxx | (1 << i);
for(intprefix : se) {
// find two pair in set
// such that a^b = newMaxx
// which is the highest
// possible bit can be obtained
if(se.count(newMaxx ^ prefix)) {
maxx = newMaxx;
break;
}
}
// clear the set for next
// iteration
se.clear();
}
returnmaxx;
}
// Driver Code
intmain()
{
intarr[] = { 25, 10, 2, 8, 5, 3 };
intn = sizeof(arr) / sizeof(arr[0]);
cout << max_xor(arr, n) << endl;
return0;
}
Java
// Java implementation of the above approach
importjava.util.*;
classGFG
{
// Function to return the
// maximum xor
staticintmax_xor(intarr[], intn)
{
intmaxx = 0, mask = 0;
HashSet<Integer> se = newHashSet<Integer>();
for(inti = 30; i >= 0; i--)
{
// set the i'th bit in mask
// like 100000, 110000, 111000..
mask |= (1<< i);
for(intj = 0; j < n; ++j)
{
// Just keep the prefix till
// i'th bit neglecting all
// the bit's after i'th bit
se.add(arr[j] & mask);
}
intnewMaxx = maxx | (1<< i);
for(intprefix : se)
{
// find two pair in set
// such that a^b = newMaxx
// which is the highest
// possible bit can be obtained
if(se.contains(newMaxx ^ prefix))
{
maxx = newMaxx;
break;
}
}
// clear the set for next
// iteration
se.clear();
}
returnmaxx;
}
// Driver Code
publicstaticvoidmain(String[] args)
{
intarr[] = { 25, 10, 2, 8, 5, 3};
intn = arr.length;
System.out.println(max_xor(arr, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the above approach
# Function to return the
# maximum xor
defmax_xor( arr , n):
maxx =0
mask =0;
se =set()
fori inrange(30, -1, -1):
# set the i'th bit in mask
# like 100000, 110000, 111000..
mask |=(1<< i)
newMaxx =maxx | (1<< i)
fori inrange(n):
# Just keep the prefix till
# i'th bit neglecting all
# the bit's after i'th bit
se.add(arr[i] & mask)
forprefix inse:
# find two pair in set
# such that a^b = newMaxx
# which is the highest
# possible bit can be obtained
if(newMaxx ^ prefix) inse:
maxx =newMaxx
break
# clear the set for next
# iteration
se.clear()
returnmaxx
# Driver Code
arr =[ 25, 10, 2, 8, 5, 3]
n =len(arr)
print(max_xor(arr, n))
# This code is contributed by ANKITKUMAR34
C#
// C# implementation of the above approach
usingSystem;
usingSystem.Collections.Generic;
classGFG
{
// Function to return the
// maximum xor
staticintmax_xor(int[]arr, intn)
{
intmaxx = 0, mask = 0;
HashSet<int> se = newHashSet<int>();
for(inti = 30; i >= 0; i--)
{
// set the i'th bit in mask
// like 100000, 110000, 111000..
mask |= (1 << i);
for(intj = 0; j < n; ++j)
{
// Just keep the prefix till
// i'th bit neglecting all
// the bit's after i'th bit
se.Add(arr[j] & mask);
}
intnewMaxx = maxx | (1 << i);
foreach(intprefix inse)
{
// find two pair in set
// such that a^b = newMaxx
// which is the highest
// possible bit can be obtained
if(se.Contains(newMaxx ^ prefix))
{
maxx = newMaxx;
break;
}
}
// clear the set for next
// iteration
se.Clear();
}
returnmaxx;
}
// Driver Code
publicstaticvoidMain(String[] args)
{
int[]arr = { 25, 10, 2, 8, 5, 3 };
intn = arr.Length;
Console.WriteLine(max_xor(arr, n));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation of the above approach
// Function to return the
// maximum xor
functionmax_xor(arr, n)
{
let maxx = 0, mask = 0;
varse = newSet();
for(let i = 30; i >= 0; i--)
{
// set the i'th bit in mask
// like 100000, 110000, 111000..
mask |= (1 << i);
for(let j = 0; j < n; ++j)
{
// Just keep the prefix till
// i'th bit neglecting all
// the bit's after i'th bit
se.add(arr[j] & mask);
}
let newMaxx = maxx | (1 << i);
//for (let prefix in se)
for(let prefix of se.keys())
{
// find two pair in set
// such that a^b = newMaxx
// which is the highest
// possible bit can be obtained
if(se.has(newMaxx ^ prefix))
{
maxx = newMaxx;
break;
}
}
// clear the set for next
// iteration
se.clear();
}
returnmaxx;
}
// Driver code
let arr = [ 25, 10, 2, 8, 5, 3 ];
let n = arr.length;
document.write(max_xor(arr, n));
// This code is contributed by target_2.
</script>
Output
28
Time Complexity: , where N is the size of the array and M is the maximum number present in the array Auxiliary Space: O(logM)
Better Approach: Another approach would be to use a Trie structure to store the bit representation of the numbers and for N terms compute the maximum XOR each can produce by going through the Trie.
The time complexity of inserting a single element into the trie is O( log(maximum element in array) ). Thus, for n elements, the time complexity of building the trie is O( n log(maximum element in array) ).
The time complexity of finding the maximum XOR for a single element in the trie is also O( log(maximum element in array) ). Thus, for n elements, the time complexity of finding the maximum XOR is O( n log(maximum element in array) ).
The space complexity of the trie is O( n log(maximum element in array) ). This is because in the worst case scenario, every bit of every element in the array needs to be stored in the trie. Since the maximum number of bits in an integer is log(maximum element in array), the space complexity is O( n log(maximum element in array) ).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!