Minimum XOR

Easy

0/40

0 upvote

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

4
2

Explanation of sample input 1:

For the first test case,

The minimum XOR of 4 corresponds to the XOR value of 5, and 1.No other pair has an XOR value less than 4.
Hence, the answer is 4. 


For the second test case:

The minimum XOR of 2 corresponds to the XOR value of 0, and 2.No other pair has an XOR value less than 2.
Hence, the answer is 2.

Sample Input 2:

2
3
31 53 64 
5
8 12 59 87 95

Sample Output 2:

42
4

Hint 1

Hint 2

Check the XOR value of every pair.

Approaches (2)

Approach 1

Approach 2

Brute Force.

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]).
Return ‘ANS’

Time Complexity

O(N^2), where ‘N’ is the number of elements in the array ‘ARR’.

In this approach, we are checking the XOR values of each pair, and there are N*(N-1) possible pairs. Hence, the overall time complexity is O(N^2).

Space Complexity

O(1).

In this approach, we are using constant space. Hence, the overall space complexity is O(1).

(100% EXP penalty)

Minimum XOR

Console