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