Last Updated: 19 Nov, 2021
Maximum XOR of Two Numbers in an Array
Moderate
Asked in companies
An array ‘A’ of ‘N’ integers is provided. Return the maximum possible number which can be created by taking bitwise XOR of any 2 integers of the array.
Example:
If the array is 2,5 and 6
2 XOR 5 is 7
2 XOR 6 is 4
5 XOR 6 is 3
Hence the answer is 7.
Input Format:
The first line contains one integer ‘N’, denoting the size of the array.
The next line contains 'N' space-separated integers representing the elements of 'A'.
Output Format:
Print a single integer in a new line denoting the maximum xor value.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Approaches
To find the maximum possible among all such pairs, we can use two nested loops to check all possible pairs and store the maximum possible xor value.
Algorithm:
- Initialise ‘ans’ to 0.
- Run a loop ‘i’ from 0 to ‘N’ - 1
- Run a loop ‘j’ from ‘i’ to ‘N’ - 1
- Update ‘ans’ to the maximum of ‘ans’ and ‘A[i]’ xor ‘A[j]’
- Return ‘ans’’
Instead of finding two elements having maximum xor, we will focus on finding the two numbers in an array, such that xor of which equals a number ‘P’. In this case, ‘P’ will be the maximum number we want to achieve till i-th bit.
For ‘P’ to be maximum, we need to try to get as many bits as possible to be 1 from left to right, left-most being the biggest bit. Note that the value of left bits is greater than the sum of all the right bits, so we will try to make bits towards the left to be 1 first, then move towards the right.
We will iterate from left to right bits and consider only the bits from left to current bit to find the optimal answer achievable for those bits. We can store only the prefix of that number till that bit by using a bitmask which will store all the bits from left to current bit for that element.
To find this, we will do bitwise AND of all elements with another number where only those bits are 1, which we need for the prefix and rest to be 0.
We will store all the prefix masks in a set and evaluate if we can make the current bit 1 in the answer.
We know if,
a xor b = c
Then
a = c xor b
So we will set the current bit 1 in a temporary answer, iterate through the set, and check if xor of this and the current element is present in the set. If it is present, we can update the answer to the temporary answer.
Algorithm:
- Initialise ‘ans’ to 0.
- Initialise ‘mask’ to 0.
- Run a loop ‘i’ from 30 to 0
- Create a set ‘s’ of integers.
- Make the ith bit 1 in the ‘mask’.
- Run a loop ‘j’ from ‘0’ to ‘N’ - 1
- Insert the bitwise and of ‘A[j]’ and ‘mask’ into the set.
- Initialise ‘tempAns’ to ‘ans’
- Make the ith bit 1 in the ‘tempAns’.
- Iterate through the set
- If xor of ‘tempAns’ and current element is present in the array, update ‘ans’ to ‘tempAns’ and break.
- Return ‘ans’