Minimum XOR value pair in Java
In this section, you will discuss about minimum XOR value pair in Java.
The objective is to enforce a value that indicates the least XOR values of the two numbers from a provided array of non-negative values.
Let us discuss a small example on obtaining the minimum XOR pair value.
Example 1:
Consider an array.
Input: Arr[] = {1, 5, 10, 15}
Now let us find out the XOR value for each pair
(1 ^ 5) = 4
(1 ^ 10)= 11
(1 ^ 15) = 14
(5 ^ 10)= 15
(5 ^ 15) = 10
(10 ^ 15)= 5
From the above observation, the pair that has the least or minimum XOR value is 4
Output: 4
Example 2:
Consider an array
Input: arr[]= {2,4,6}
Now let us find out the XOR value for each pair
(2 ^ 4)= 6
(2 ^ 6)= 4
(4 ^ 6)= 2
From the above observation, the pair that has the least or minimum XOR value is 2
Output: 2
There are basically three ways in which the minimum XOR pair value is achieved. They probably are
- Simple method
- Sorting method
- TRIE method
Simple Method
Finding every pair of elements existing in the given sequence is the simple strategy. Finding the smallest XOR value by computing the XOR for each pair. The generation of all the pairs in the provided array is a Simple Solution. Return the smallest possible XOR value. It takes this solution O(n2) time.
Let us understand the simple method with an example program
File name: Simplem.java
// A Java application to determine the least XOR output in an array.
Class Simlpem{
// Returns minimum XOR value of pair in arr[0..n-1]
static int minXOR(int arr[], int n)
{
int min_XOR = Integer.MAX_VALUE; // Initialize result
// Acquire each pair in the given array.
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
// Update the least XOR value if necessary.
min_XOR = Math.min(min_XOR, arr[i] ^ arr[j]);
return min_XOR;
}
public static void main(String args[])
{
int arr[] = { 1,5,10,15 };
int n = arr.length;
System.out.println(minXOR(arr, n));
}
}Output
4
Sorting Method
This method uses a single loop to obtain the minimal XOR value while sorting the input array. The reason the sorting strategy works is that the XOR for two integers that are close to one another has a lesser XOR value than the XOR for two integers that are far apart. Since the numbers that seem to be closer to just one another come following each other while sorting, all we need to do is execute a single loop to discover the XOR of the subsequent elements.
Let us understand it with a simple example program
File name: Sortm.java
import java.util.Arrays;
class Sortm {
// A method to determine the smallest XOR pair
static int minXOR(int arr[], int n)
{
// organizing the provided array
Arrays.parallelSort(arr);
int minXOR = Integer.MAX_VALUE;
int val = 0;
// generates the minimum XOR of the very next pairs.
for (int i = 0; i < n - 1; i++) {
val = arr[i] ^ arr[i + 1];
minXOR = Math.min(minXOR, val);
}
return minXOR;
}
public static void main(String args[])
{
int arr[] = { 2, 4, 6};
int n = arr.length;
System.out.println(minXOR(arr, n));
}
}
Output
2
TRIE Method
Since TRIE allows us to solve the problem faster than O(nlog(n)), we will obtain the most optimal result.
The following is the algorithm for the above method
- Create an empty TRIE with two children per node, one for the 0 bit and the second for the 1 bit.
- Add a[0] into TRIE after initialising minXORVal as INT MAX.
- Beginning with the second element, go through each element of the array one at a time and complete the following:
- Start by looking for the TRIE's standard minimum bit value difference. The current element is then XORed with the standard minimum bit that deviates from that value.
- If necessary, update the minXORVal value.
- Add the array's current element.
- give the minXORVal back
Let us understand it with an example program
File name: Triem.java
// Java program to determine the array's minimal XOR value.
class Triem {
static final int INT_SIZE = 32;
static class TrieNode {
int value; // used in leaf node
TrieNode[] Child = new TrieNode[2];
public TrieNode()
{
value = 0;
Child[0] = null;
Child[1] = null;
}
}
static TrieNode root;
// utility function insert new key in trie
static void insert(int key)
{
TrieNode temp = root;
// Start with the most important bit and enter each essential bit one at a time into the trie
for (int i = INT_SIZE - 1; i >= 0; i--) {
// In the provided prefix, find the current bit.
int current_bit = (key & (1 << i)) >= 1 ? 1 : 0;
if (temp != null && temp.Child[current_bit] == null)
temp.Child[current_bit] = new TrieNode();
temp = temp.Child[current_bit];
}
// continue to keep at leafNode
temp.value = key;
}
static int minXORUtil(int key)
{
TrieNode temp = root;
for (int i = INT_SIZE - 1; i >= 0; i--) {
// In the provided prefix, find the current bit.
int current_bit = (key & (1 << i)) >= 1 ? 1 : 0;
if (temp.Child[current_bit] != null)
temp = temp.Child[current_bit];
else if (temp.Child[1 - current_bit] != null)
temp = temp.Child[1 - current_bit];
}
return key ^ temp.value;
}
static int minXOR(int arr[], int n)
{
int min_XOR = Integer.MAX_VALUE; // Initialize result
// make a True, then add the first element to it.
root = new TrieNode();
insert(arr[0]);
// For each number, iterate through all array elements to get the minimum XOR.
for (int i = 1; i < n; i++) {
min_XOR = Math.min(min_XOR, minXORUtil(arr[i]));
insert(arr[i]);
}
return min_XOR;
}
public static void main(String args[])
{
int arr[] = { 2, 4, 6};
int n = arr.length;
System.out.println(minXOR(arr, n));
}
}Output
2