Last Updated: 21 Nov, 2021
Minimum XOR
Easy
Asked in companies
Ninja is learning the bitwise operations to score well in his class test. He found an interesting question on bitwise XOR. The problem statement is as follows:
An array ‘ARR’ consists of ‘N’ numbers. The task is to find pair having the minimum XOR value.No, need to print the values of the element. Just print the minimum XOR value. Can you help Ninja to solve this problem?
For Example
If the array ‘ARR’ is [13,5,11,1], the answer will be 4, corresponding to the XOR value of 1 and 5.
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 a single integer ‘N’ corresponding to the number of elements in the array.
The next line of each test case contains the array ‘ARR’.
Output Format:
For each test case, print ‘an integer corresponding to the minimum XOR value.
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^5
1 <= ARR[i] <= 10^9.
Time limit: 1 sec
Approaches
In this approach, we will simply check the XOR value of each pair and find the minimum XOR value among them.
Algorithm:
- Declare ‘ANS’ to store the required answer.
- Set ‘ANS’ as INF(A large value).
- For i in range 0 to ‘N’-1, do the following:
- For j in range i+1 to ‘N’-1:
- Set ‘ANS‘ as the minimum of ‘ANS’ and (ARR[i] XOR ARR[j]).
- For j in range i+1 to ‘N’-1:
- Return ‘ANS’
Intuition:
If A <= B <= C, then:
either (A XOR B) is less than (A XOR C).
or (B XOR C) is less than (A XOR C).
Proof:
Let binary representation of A is ‘11000….01’.
Let binary representation of B is ‘11000….01’.
Let binary representation of C is ‘11010….01’.
In this case, the leftmost bit where A and C are mismatching is the 4th bit from the left, and the 4th bit of ‘B’ is not set.
So, A XOR C will be ‘00010…..’ and A XOR B will be ‘0000……’.So, in this case, A XOR B is less than A XOR C.
Let binary representation of A is ‘11000….01’.
Let binary representation of B is ‘11010….01’.
Let binary representation of C is ‘11010….01’.
In this case, the leftmost bit where A and C are mismatching is the 4th bit from the left, and the 4th bit of ‘B’ is set.
So, A XOR C will be ‘00010…..’ and B XOR C will be ‘0000……’.So, in this case, B XOR C is less than A XOR C.
Hence, with this proof, we can say that the minimum XOR value will be among the XOR value of adjacent elements if the array is sorted.
In this approach, we will first sort the elements, and this time we will just check the XOR values of adjacent elements and find the minimum value among them.
Algorithm:
- Sort the array ‘ARR’.
- Declare ‘ANS’ to store the required answer.
- Set ‘ANS’ as INF(A large value).
- For i in range 0 to ‘N’-2, do the following:
- Set ‘ANS‘ as the minimum of ‘ANS’ and (ARR[i] XOR ARR[i+1]).
- Return ‘ANS’
Similar problems