Last Updated: 8 Dec, 2020
Maximum XOR
Hard
Asked in companies
You are given two arrays of non-negative integers say ‘arr1’ and ‘arr2’. Your task is to find the maximum value of ( ‘A’ xor ‘B’ ) where ‘A’ and ‘B’ are any elements from ‘arr1’ and ‘arr2’ respectively and ‘xor’ represents the bitwise xor operation.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, 'N' and ‘M’ denoting the number of elements in the first and second array.
The second line of each test case contains 'N' space-separated integers denoting the elements of the array first array.
The last line of each test case contains 'M' space-separated integers denoting the elements of the array second array.
Output Format:
For each test case, print a single integer - the maximum possible xor among all possible pairs.
Print the output of each test case in a separate line.
Note :
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N, M <= 1000
0 <= arr1[i], arr2[i] <= 10 ^ 9
Where 'T' denotes the number of test cases, 'N', ‘M’ denotes the number of elements in the first array and second array, ‘arr1[i]', and ‘arr2[i]’ denotes the 'i-th' element of the first array and second array.
Time limit: 1 sec
Approaches
SImply iterate over all possible pairs and find the maximum possible xor value.
Algorithm:
- Let the given array be ‘arr1’ and ‘arr2’.
- Declare a variable say ‘maxXor’. And initialize it with 0.
- Run a loop form ‘i’ = 0 to length of ‘arr1’ - 1.
- Run a loop from ‘j’ = 0 to length of ‘arr2’ - 1.
- If ( ‘arr1[i]’ xor ‘arr2[j]’ ) > maxXor, then update ‘maxXor’ , i.e. do ‘maxXor’ = ( ‘arr1[i]’ xor ‘arr2[j]’ ).
- Run a loop from ‘j’ = 0 to length of ‘arr2’ - 1.
- Return ‘maxXor’.
We can maximize the bitwise ‘xor’ value for any two integers by taking their bits at ‘i- th’ position as 1 and 0 or 0 and 1. For an integer ‘X’ in binary representation, we start from its most significant bit and try to find a corresponding number ‘Y’ from available numbers such that bits at the current position of ‘X’ and ‘Y’ are different, in this way we could maximize the bitwise xor value for ‘X’. So for a 32-bit integer, we just need to iterate through all its bits and check for a corresponding integer from another array such that their xor value is maximum.
To efficiently check for the corresponding integer value in the second array we can maintain a binary trie data structure for each element in the second array. For each element in the second array we convert it into binary representation and insert the bit string into the trie. The most significant bit will be the root.
So the idea is to iterate through each element in the first array and convert it into its binary representation and iterate through its all bits starting from the most significant bit. If the current bit is ‘1’ then we move to ‘0’ child in trie if available and vice versa. At last, we will find a corresponding integer from the second array such that its xor value with the current element of the first array is maximum. At last, we will return the maximum of all such values.
Algorithm:
- Let the given array be ‘arr1’ and ‘arr2’.
- Declare a variable say ‘maxXor’. And initialize it with 0.
- Create a trie data structure to store the binary representation of 32-bit integers.
- Run a loop form ‘i’ = 0 to the length of ‘arr1’ - 1. to traverse the elements in ‘arr1’.
- Insert the binary representation of ‘arr1[i]’ into the trie.
- Create a function say ‘findMax’ to find the maximum xor value for a given integer from trie.
- Run a loop form ‘i’ = 0 to the length of ‘arr2’ - 1 to traverse the elements in ‘arr2’.
- If ‘maxXor’ < ‘findMax(arr2[i])’, then update ‘maxXor’ , i.e. do ‘maxXor’ = ‘findMax( arr2[i] )’.
- Return ‘maxXor.
Description of ‘findMax’ function
The function will take two parameters:
- key: int value for which corresponding max xor value is to find.
- root: Root node of the trie data structure.
bool findMax ( ‘root’ , ‘key’ ):
- Declare a trie node variable say ‘temp’ to traverse the trie.
- Initialize the ‘temp’ with root.
- Run a loop from the most significant bit i.e 32 to 0.
- Let the current bit in ‘key’ is ‘currBit’.
- If ‘temp’ has a child with the opposite bit of ‘currBit’ that means that trie contains an integer that has a different bit at ‘i -th’ position, so move ‘temp’ to ‘temp’ -> child[1 ^ ‘currBit’].
- Else, there is no integer in trie that has the opposite bit at ‘i-th’ position, so now move ‘temp’ to ‘temp’ -> child[‘currBit’].
- Now we have reached the leaf node of trie that contains an integer such that its xor value with ‘key’ is max possible.
- So return (‘temp -> value’ xor ‘key’).