Maximum difference between groups of size two

0 0 7 minutes read

Given an array of even number of elements, form groups of 2 using these array elements such that the difference between the group with highest sum and the one with lowest sum is maximum.

Note: An element can be a part of one group only and it has to be a part of at least 1 group.

Examples:

Input : arr[] = {1, 4, 9, 6}
Output : 10
Groups formed will be (1, 4) and (6, 9), 
the difference between highest sum group
(6, 9) i.e 15 and lowest sum group (1, 4)
i.e 5 is 10.

Input : arr[] = {6, 7, 1, 11}
Output : 11
Groups formed will be (1, 6) and (7, 11), 
the difference between highest sum group
(7, 11) i.e 18 and lowest sum group (1, 6)
i.e 7 is 11.

Simple Approach: We can solve this problem by making all possible combinations and checking each set of combination differences between the group with the highest sum and with the lowest sum. A total of n*(n-1)/2 such groups would be formed (nC2).

Time Complexity: O(n^3), because it will take O(n^2) to generate groups and to check against each group n iterations will be needed thus overall it takes O(n^3) time.

Efficient Approach: We can use the greedy approach. Sort the whole array and our result is sum of last two elements minus sum of first two elements.

Implementation:

C++

// CPP program to find minimum difference
// between groups of highest and lowest
// sums.
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
ll CalculateMax(ll arr[], int n)
{
    // Sorting the whole array.
    sort(arr, arr + n);
    
    int min_sum = arr[0] + arr[1];
    int max_sum = arr[n-1] + arr[n-2];
 
    return abs(max_sum - min_sum);
}
 
// Driver code
int main()
{
    ll arr[] = { 6, 7, 1, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << CalculateMax(arr, n) << endl;
    return 0;
}

Java

// Java program to find minimum difference 
// between groups of highest and lowest 
// sums. 
import java.util.Arrays; 
import java.io.*;
 
class GFG {
static int  CalculateMax(int  arr[], int n) 
{ 
    // Sorting the whole array. 
    Arrays.sort(arr); 
     
    int min_sum = arr[0] + arr[1]; 
    int max_sum = arr[n-1] + arr[n-2]; 
 
    return (Math.abs(max_sum - min_sum)); 
} 
 
// Driver code
     
    public static void main (String[] args) {
 
    int arr[] = { 6, 7, 1, 11 }; 
    int n = arr.length; 
    System.out.println (CalculateMax(arr, n)); 
    }
}

Python3

# Python 3 program to find minimum difference 
# between groups of highest and lowest 
def CalculateMax(arr, n):
 
    # Sorting the whole array.
    arr.sort()
    min_sum = arr[0] + arr[1]
    max_sum = arr[n - 1] + arr[n - 2]
    return abs(max_sum - min_sum)
 
# Driver code
arr = [6, 7, 1, 11]
n = len(arr)
print(CalculateMax(arr, n))
 
# This code is contributed
# by Shrikant13

C#

// C# program to find minimum difference 
// between groups of highest and lowest 
// sums.
using System;
 
public class GFG{
 
static int CalculateMax(int []arr, int n) 
{ 
    // Sorting the whole array. 
    Array.Sort(arr); 
     
    int min_sum = arr[0] + arr[1]; 
    int max_sum = arr[n-1] + arr[n-2]; 
 
    return (Math.Abs(max_sum - min_sum)); 
} 
 
// Driver code
     
    static public void Main (){
    int []arr = { 6, 7, 1, 11 }; 
    int n = arr.Length; 
    Console.WriteLine(CalculateMax(arr, n)); 
    }
//This code is contributed by Sachin.    
}

PHP

<?php
// PHP program to find minimum 
// difference between groups of 
// highest and lowest sums.
function CalculateMax($arr, $n)
{
    // Sorting the whole array.
    sort($arr);
     
    $min_sum = $arr[0] + 
               $arr[1];
    $max_sum = $arr[$n - 1] + 
               $arr[$n - 2];
 
    return abs($max_sum -
               $min_sum);
}
 
// Driver code
$arr = array (6, 7, 1, 11 );
$n = sizeof($arr);
echo CalculateMax($arr, $n), "\n" ;
 
// This code is contributed by ajit
?>

Javascript

<script>
 
    // Javascript program to 
    // find minimum difference 
    // between groups of highest and lowest 
    // sums.
     
    function CalculateMax(arr, n) 
    { 
        // Sorting the whole array. 
        arr.sort(function(a, b){return a - b});
 
        let min_sum = arr[0] + arr[1]; 
        let max_sum = arr[n-1] + arr[n-2]; 
 
        return (Math.abs(max_sum - min_sum)); 
    } 
     
    let arr = [ 6, 7, 1, 11 ]; 
    let n = arr.length; 
    document.write(CalculateMax(arr, n));
         
</script>

Output

Time Complexity: O (n * log n)

Auxiliary Space: O(1)

Further Optimization : Instead of sorting, we can find a maximum two and minimum of two in linear time and reduce the time complexity to O(n).

Implementation:

C++

// CPP program to find minimum difference
// between groups of highest and lowest
// sums.
#include <bits/stdc++.h>
using namespace std;
 
int CalculateMax(int arr[], int n)
{
     
    int first_min = INT_MAX;
    int second_min = INT_MAX;
    for(int i = 0; i < n ; i ++)
    {
        /* If current element is smaller than first
        then update both first and second */
        if (arr[i] < first_min)
        {
            second_min = first_min;
            first_min = arr[i];
        }
  
        /* If arr[i] is in between first and second
        then update second */
        else if (arr[i] < second_min && arr[i] != first_min)
            second_min = arr[i];
    }
     
    int first_max = INT_MIN;
    int second_max = INT_MIN;
    for (int i = 0; i < n ; i ++)
    {
        /* If current element is smaller than first
        then update both first and second */
        if (arr[i] > first_max)
        {
            second_max = first_max;
            first_max = arr[i];
        }
  
        /* If arr[i] is in between first and second
        then update second */
        else if (arr[i] > second_max && arr[i] != first_max)
            second_max = arr[i];
    }
     
    return abs(first_max+second_max-first_min-second_min);
     
}
 
// Driver code
int main()
{
    int arr[] = { 6, 7, 1, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << CalculateMax(arr, n) << endl;
    return 0;
}
 
// This code is contributed by Pushpesh Raj

Java

// Java program to find minimum difference
// between groups of highest and lowest
// sums.
import java.util.Arrays;
import java.io.*;
 
class GFG {
static int CalculateMax(int arr[], int n)
{
    int first_min = Integer.MAX_VALUE;
    int second_min = Integer.MAX_VALUE;
    for(int i = 0; i < n ; i ++)
    {
        /* If current element is smaller than first
        then update both first and second */
        if (arr[i] < first_min)
        {
            second_min = first_min;
            first_min = arr[i];
        }
  
        /* If arr[i] is in between first and second
        then update second */
        else if (arr[i] < second_min && arr[i] != first_min)
            second_min = arr[i];
    }
     
    int first_max = Integer.MIN_VALUE;
    int second_max = Integer.MIN_VALUE;
    for (int i = 0; i < n ; i ++)
    {
        /* If current element is smaller than first
        then update both first and second */
        if (arr[i] > first_max)
        {
            second_max = first_max;
            first_max = arr[i];
        }
  
        /* If arr[i] is in between first and second
        then update second */
        else if (arr[i] > second_max && arr[i] != first_max)
            second_max = arr[i];
    }
     
    return Math.abs(first_max+second_max-first_min-second_min);
}
 
// Driver code
     
    public static void main (String[] args) {
 
    int arr[] = { 6, 7, 1, 11 };
    int n = arr.length;
    System.out.println (CalculateMax(arr, n));
    }
}

Python3

# Python 3 program to find minimum difference
# between groups of highest and lowest
def CalculateMax(arr, n):
 
    # maxint constant
    first_min = 99999
    second_min = 99999
 
    for i in range(n):
        if arr[i] < first_min:
            second_min = first_min
            first_min = arr[i]
        # If arr[i] is in between first and second
        # then update second
 
        elif arr[i] < second_min & arr[i] != first_min:
            second_min = arr[i]
 
    # maxint constant
    first_max = -99999
    second_max = -99999
 
    for i in range(n):
        if arr[i] > first_max:
            second_max = first_max
            first_max = arr[i]
        # If arr[i] is in between first and second
        # then update second
 
        elif arr[i] > second_max & arr[i] != first_max:
            second_max = arr[i]
 
    return abs(first_max+second_max-first_min-second_min)
 
 
# Driver code
arr = [6, 7, 1, 11]
n = len(arr)
print(CalculateMax(arr, n))
 
# This code is contributed Aarti_Rathi

C#

// C# program to find minimum difference
// between groups of highest and lowest
// sums.
using System;
 
public class GFG{
 
static int CalculateMax(int []arr, int n)
{
    int first_min = int.MaxValue;
    int second_min = int.MaxValue;
    for(int i = 0; i < n ; i ++)
    {
        /* If current element is smaller than first
        then update both first and second */
        if (arr[i] < first_min)
        {
            second_min = first_min;
            first_min = arr[i];
        }
  
        /* If arr[i] is in between first and second
        then update second */
        else if (arr[i] < second_min && arr[i] != first_min)
            second_min = arr[i];
    }
     
    int first_max = int.MinValue;
    int second_max = int.MinValue;
    for (int i = 0; i < n ; i ++)
    {
        /* If current element is smaller than first
        then update both first and second */
        if (arr[i] > first_max)
        {
            second_max = first_max;
            first_max = arr[i];
        }
  
        /* If arr[i] is in between first and second
        then update second */
        else if (arr[i] > second_max && arr[i] != first_max)
            second_max = arr[i];
    }
     
    return Math.Abs(first_max+second_max-first_min-second_min);
}
 
// Driver code
     
    static public void Main (){
    int []arr = { 6, 7, 1, 11 };
    int n = arr.Length;
    Console.WriteLine(CalculateMax(arr, n));
    }
}

Javascript

<script>
 
    // Javascript program to
    // find minimum difference
    // between groups of highest and lowest
    // sums.
     
    function CalculateMax(arr, n)
    {
    let first_min = Number.MAX_VALUE;
    let second_min = Number.MAX_VALUE;
    for(let i = 0; i < n ; i ++)
    {
        /* If current element is smaller than first
        then update both first and second */
        if (arr[i] < first_min)
        {
            second_min = first_min;
            first_min = arr[i];
        }
  
        /* If arr[i] is in between first and second
        then update second */
        else if (arr[i] < second_min && arr[i] != first_min)
            second_min = arr[i];
    }
     
    let first_max = Number.MIN_VALUE;
    let second_max = Number.MIN_VALUE;
    for (let i = 0; i < n ; i ++)
    {
        /* If current element is smaller than first
        then update both first and second */
        if (arr[i] > first_max)
        {
            second_max = first_max;
            first_max = arr[i];
        }
  
        /* If arr[i] is in between first and second
        then update second */
        else if (arr[i] > second_max && arr[i] != first_max)
            second_max = arr[i];
    }
     
    return Math.abs(first_max+second_max-first_min-second_min);
    }
     
    let arr = [ 6, 7, 1, 11 ];
    let n = arr.length;
    document.write(CalculateMax(arr, n));
         
</script>

Output

Complexity Analysis:

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!