Minimum Difference Between Groups of Size Two in Java
There is given an array with various integers in it. The goal is to divide the elements into distinct groups, each of which has just two, so that the difference between the groups with the highest and lowest sums is as small as possible. Keep in mind that each element can only belong to one group. Additionally, leaving any piece is prohibited. To put it another way, an element must belong to a group.
Example
int a [ ] = {4, 7 , 0 , 2 , 3 , 6}
Explanation
G1 = {4, 6}, G2 = {0, 2}, G3 = {7, 6}, G4 = {7, 3}
G1 = 4 + 6 = 10 , G2 = 0 + 2 = 2 , G3 = 7 + 6 = 13 , G4 = 7 + 3 = 10
As a result, we can observe that the minimum sum is 2 and maximum sums is 13. The difference is therefore 13-2 = 11.
Approach
The process is easy. To ensure that the distance between the maximum and minimum is as little as possible, one must maintain the maximum at the lowest value and the minimum at the greatest value. To achieve this, we must combine the array's integers in a way that the largest element is mapped to the smallest element, and the second largest element is mapped to the largest element. The array must be sorted before the final member is combined (made into a group) with the first element, the second-last element with the second element, and so forth.
Java Program to find minimum difference between groups of size of two
MinDiff.java
// important import statement
import java.util.Arrays;
import java.util.ArrayList;
public class Mindiff
{
private int Min ( int a , int b )
{
if ( a > b )
{
return b;
}
return a;
}
private int Max ( int x , int y )
{
if ( x > y )
{
return x ;
}
return y ;
}
public int MinDiff ( int arr[] , int s1 )
{
if ( s1 % 2 != 0 )
{
return -1 ;
}
Arrays . sort ( arr ) ;
int dif = Integer . MAX_VALUE ;
ArrayList < Integer > a = new ArrayList < Integer > ( ) ;
for ( int j = 0 , k = s1 - 1 ; j < k ; k-- , j++ )
{
a . add ( arr [ j ] + arr [ k ] ) ;
}
int min = Integer . MAX_VALUE ;
int max = Integer . MIN_VALUE ;
int size = a . size ( ) ;
for ( int j = 0 ; j < size ; j++ )
{
min = Min ( min , a . get ( j ) ) ;
max = Max(max, a.get(j));
}
return (max - min);
}
public static void main(String[] args)
{
Main obj = new Main();
int a [] = { 1 , 2 , 4 , 6 , 10 , 11 , 23 , 7 } ;
int size_Of_array = a . length ;
System.out.println("Input array: ");
for(int i = 0; i < size_Of_array; i++)
{
System.out.print(a[i] + " ");
}
System.out.println();
int ans = obj.MinDiff(a, size_Of_array);
if(ans != -1)
{
System.out.println(" Minimum difference : " + ans);
}
else
{
System.out.println("It is not possible to find the minimum difference.");
}
System.out.println("\n");
int a1[] = {4, 11, 5, 3, 7, 2};
size_Of_array = a1.length;
System.out.println("For the input array: ");
for(int i = 0; i < size_Of_array; i++)
{
System.out.print(a1[i] + " ");
}
System . out . println();
ans = obj . MinDiff ( a1 , size_Of_array ) ;
if ( ans != -1 )
{
System . out . println (" Minimum difference : " + ans ) ;
}
else
{
System . out . println (" Not possible to find the minimum difference. " ) ;
}
System . out . println ( " \n ") ;
int a2 [ ] = { 3 , 2 , 1 , 0 , 34 , 20 , 35 } ;
size_Of_array = a2 . length ;
System . out . println ( " For the input array: " ) ;
for ( int i = 0 ; i < size_Of_array ; i++ )
{
System . out . print ( a2 [ i ] + " " ) ;
}
System . out . println ( ) ;
ans = obj . MinDiff ( a2 , size_Of_array ) ;
if ( ans != -1 )
{
System . out . println( " The minimum difference is: " + ans ) ;
}
else
{
System . out . println ( " It is not possible to find the minimum difference. " ) ;
}
System . out . println ( " \n " ) ;
}
}
Output

Another Approach to find minimum difference between groups of size two in Java.
MinDiff2.java
import java.io.*;
import java.util.*;
class MinDiff2 {
static int cal ( int[] arr , int n )
{
Arrays . sort ( arr ) ;
int min = arr [ 0 ] + arr [ n - 1 ] ;
int max = arr [ 0 ] + arr [ n - 1 ] ;
for ( int j = 1, k = n - 1; j < k; j++, k --) {
if ( arr [ j ] + arr [ k ] > max )
{
max = arr [ j ] + arr [ k ] ;
}
if (arr [ j ] + arr [ k ] < min )
{
min = arr [ j ] + arr [ k ];
}
}
return Math . abs ( max - min ) ;
}
public static void main ( String [ ] args )
{
int [ ] a = { 12 , 16 , 24 , 23 } ;
int len = a . length ;
System . out . print ( cal ( a , len ) ) ;
}
}
Output
