Minimum XOR Value Pair in Java

10 Sept 2024 | 8 min read

Given an array containing non-negative numbers, our task is to find out a value that represents the minimum XOR value of two numbers from the given array. Consider the following examples.

Example 1:

Input: int a[] = {10, 8, 5, 3, 1};

Output: 2

Explanation: In the given array, we can make 10 pairs

(10, 8) = 10 ^ 8 = 2		(10, 5) = 10 ^ 5 = 15
(10, 3) = 10 ^ 3 = 9		(10, 1) = 10 ^ 1 = 11
(8, 5) = 8 ^ 5 = 13		(8, 3) = 8 ^ 3 = 11
(8, 1) = 8 ^ 1 = 9		(5, 3) = 5 ^ 3 = 6
(5, 1) = 5 ^ 1 = 4		(3, 1) = 3 ^ 1 = 2

We see that the minimum XOR value of all the above pairs is 2.
Note that there is no need to make another pair (8, 10). It is because the XOR operation is commutative, and pair (10, 8) has already been considered.

Example 2:

Input: int a[] = {3, 5, 7, 2};

Output: 1

Explanation: In the given array, we can make 6 pairs.

(3, 5) = 3 ^ 5 = 6		(3, 7) = 3 ^ 7 = 4
(3, 2) = 3 ^ 2 = 1		(5, 7) = 5 ^ 7 = 2
(5, 2) = 5 ^ 2 = 7		(7, 2) = 7 ^ 2 = 5

We see that the minimum XOR value of all the above pairs is 1.

Naive Approach

The approach is straightforward, find out every pair of the elements present in the given array. Compute the XOR for every pair and find out the minimum XOR value. Let's see it happening in the following program.

FileName: MinXORVal.java

Output:

For the array: 
10 8 5 3 1 
The minimum XOR value is: 2

For the array: 
3 5 7 2 
The minimum XOR value is: 1

Time Complexity: In the above program, we have used two-degree nesting of the for-loops in the method findMinXorVal(). Since for each iteration of the outer loop, the inner loop has a time complexity of O(n). Therefore, the overall time complexity of the program is O(n2), where n is the total number of elements present in the input array.

Using Sorting

In this approach, we will sort the input array and will find the minimum XOR value using a single loop. The sorting approach works because the XOR of two numbers that are nearer to each other has a lower XOR value as compared to the numbers that are distant. For example: 1 ^ 8 = 9 & 4 ^ 5 = 1. It is because the gap between 4 & 5 is 1 and 1 & 8 is 7. Therefore, when we do sorting, the numbers that are nearer to one another come one after the other, and then all we have to do is to run a single loop and find XOR of consecutive elements. Observe the following program.

FileName: MinXORVal1.java

Output:

For the array: 
10 8 5 3 1 
The minimum XOR value is: 2
For the array: 
3 5 7 2 
The minimum XOR value is: 1

Time Complexity: In the above program, we have used sorting and a single for-loop. Sorting takes O(nlog(n)) time, and the loop takes O(n) time. Therefore, the overall time complexity of the above program is O(n + nlog(n)), where n is the total number of elements present in the input array. Note that this approach is better than the previous one.

Using TRIE

Using TRIE, we will get the most optimized solution as we can solve the problem in even lesser time than O(nlog(n)). Let's see the algorithm of it.

Step 1: Make an empty TRIE such that each node of the TRIE has two children, one for the 0 and the other for the 1 bit.

Step 2: Do the Initialization of minXorVal as INT_MAX, and insert a[0] into TRIE.

Step 3: Traverse all the elements of the array one by one, beginning from the second element, and do the following:

First, look for the minimum set bit value difference in TRIE. Then do the XOR of the current element with the minimum set bit that differs from that value.
Update the minXorVal value, if required
Insert the current element of the array

Step 4: return the minXorVal

FileName: MinXORVal2.java

Output:

For the array: 
10 8 5 3 1 
The minimum XOR value is: 2

For the array: 
3 5 7 2 
The minimum XOR value is: 1

Time Complexity: The time complexity of the above program is O(n), where n is the total number of elements present in the array.

Next TopicIccanobif Numbers in Java

← prev next →

We provides tutorials and interview questions of all technology like java tutorial, android, java frameworks

Contact info

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

+91-9599086977

Java Conversion

Java Misc

Minimum XOR Value Pair in Java

Naive Approach

Using Sorting

Using TRIE

Related Posts

Subscribe to Tpoint Tech

Contact info

Follow us

Tutorials

Interview Questions

Online Compiler