Minimum and Maximum sum of absolute differences of pairs
Given an array of N integers where N is even, find the minimum and maximum sum of absolute difference of N/2 pairs formed by pairing every element with one other element.
Examples:
Input: a[] = {10, -10, 20, -40} Output: min_sum = 40, max_sum = 80 Explanation: Pairs selected for minimum sum (-10, -40) and (10, 20) min_sum = |-10 - -40| + |20 - 10| = 40 Pairs selected for maximum sum (-10, 20) and (-40, 10) max_sum = |-10 - 20| + |10 - -40| = 80 Input: a[] = {20, -10, -1, 30} Output: min_sum = 19, max_sum = 61 Explanation: Pairs selected for minimum sum (-1, -10) and (20, 30) min_sum = |-1 - -10| + |20 - 30| = 19 Pairs selected for maximum sum (-1, 30) and (-10, 20) max_sum = |-1 - 30| + |-10 - 20| = 61
Approach: The most common observation will be that for minimum sum of differences we need the closest elements together as a pair and for the maximum sum we need the farthest elements together as a pair. So, we can simply sort the given list of elements and the closest pairs will be a[i], a[i+1], their absolute difference sum will yield us the minimum sum. The farthest will be (a[0], a[n-1]) and (a[1], a[n-2]) and so on, and their absolute difference sum will yield us the maximum-sum.
Implementation:
C++
// CPP program to find minimum and maximum // sum of absolute differences of pairs #include <bits/stdc++.h> using namespace std; // function to calculate minimum sum int calculate_min_sum( int a[], int n) { // sorts the array c++ stl sort(a, a + n); // initially min=0 and max=0 int min_sum = 0; // traverse to find the minimum sum for ( int i = 1; i < n; i += 2) { // the adjacent elements difference // will always be smaller min_sum += abs (a[i] - a[i - 1]); } return min_sum; } // function to calculate maximum sum int calculate_max_sum( int a[], int n) { // sorts the array c++ stl sort(a, a + n); int max_sum = 0; // traverse to find the maximum sum for ( int i = 0; i < n / 2; i++) { // the farthest distant elements sum // will always be maximum max_sum += abs (a[n - 1 - i] - a[i]); } return max_sum; } // Driver program to test above function int main() { int a[] = { 10, -10, 20, -40}; int n = sizeof (a) / sizeof (a[0]); cout << "The minimum sum of pairs is " << calculate_min_sum(a, n) << endl; cout << "The maximum sum of pairs is " << calculate_max_sum(a, n) << endl; return 0; } |
Java
// Java program to find minimum and maximum // sum of absolute differences of pairs import java.util.Arrays; class GFG { // function to calculate minimum sum static int calculate_min_sum( int [] a, int n) { // sorts the array c++ stl Arrays.sort(a); // initially min=0 and max=0 int min_sum = 0 ; // traverse to find the minimum sum for ( int i = 1 ; i < n; i += 2 ) { // the adjacent elements difference // will always be smaller min_sum += Math.abs(a[i] - a[i - 1 ]); } return min_sum; } // function to calculate maximum sum static int calculate_max_sum( int [] a, int n) { // sorts the array c++ stl Arrays.sort(a); int max_sum = 0 ; // traverse to find the maximum sum for ( int i = 0 ; i < n / 2 ; i++) { // the farthest distant elements sum // will always be maximum max_sum += Math.abs(a[n - 1 - i] - a[i]); } return max_sum; } // Driver program to test above function public static void main (String[] args) { int [] a = { 10 , - 10 , 20 , - 40 }; int n = a.length; System.out.println( "The minimum sum of pairs is " + calculate_min_sum(a, n)); System.out.println( "The maximum sum of pairs is " + calculate_max_sum(a, n)); } } /* This code is contributed by Mr. Somesh Awasthi */ |
Python3
# Python 3 program to find minimum and maximum # sum of absolute differences of pairs # function to calculate minimum sum def calculate_min_sum( a, n): # sorts the array c++ stl a.sort() # initially min=0 and max=0 min_sum = 0 # traverse to find the minimum sum for i in range ( 1 , n, 2 ): # the adjacent elements difference # will always be smaller min_sum + = abs (a[i] - a[i - 1 ]) return min_sum # function to calculate maximum sum def calculate_max_sum(a, n): # sorts the array c++ stl a.sort() max_sum = 0 # traverse to find the maximum sum for i in range (n / / 2 ): # the farthest distant elements sum max_sum + = abs (a[n - 1 - i] - a[i]) return max_sum # Driver Code if __name__ = = "__main__" : a = [ 10 , - 10 , 20 , - 40 ] n = len (a) print ( "The minimum sum of pairs is" , calculate_min_sum(a, n)) print ( "The maximum sum of pairs is" , calculate_max_sum(a, n)) # This code is contributed by ita_c |
C#
// C# program to find minimum and maximum // sum of absolute differences of pairs using System; class GFG { // function to calculate minimum sum static int calculate_min_sum( int []a, int n) { // sorts the array c++ stl Array.Sort(a); // initially min=0 and max=0 int min_sum = 0; // traverse to find the minimum sum for ( int i = 1; i < n; i += 2) { // the adjacent elements difference // will always be smaller min_sum += Math.Abs(a[i] - a[i - 1]); } return min_sum; } // Function to calculate maximum sum static int calculate_max_sum( int []a, int n) { // sorts the array c++ stl Array.Sort(a); int max_sum = 0; // Traverse to find the maximum sum for ( int i = 0; i < n / 2; i++) { // the farthest distant elements sum // will always be maximum max_sum += Math.Abs(a[n - 1 - i] - a[i]); } return max_sum; } // Driver Code public static void Main () { int []a = { 10, -10, 20, -40}; int n = a.Length; Console.WriteLine( "The minimum sum of pairs is " + calculate_min_sum(a, n)); Console.Write( "The maximum sum of pairs is " + calculate_max_sum(a, n)); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to find minimum and maximum // sum of absolute differences of pairs // function to calculate minimum sum function calculate_min_sum( $a , $n ) { // sorts the array c++ stl sort( $a ); // initially min=0 and max=0 $min_sum = 0; // traverse to find the minimum sum for ( $i = 1; $i < $n ; $i += 2) { // the adjacent elements difference // will always be smaller $min_sum += abs ( $a [ $i ] - $a [ $i - 1]); } return $min_sum ; } // function to calculate maximum sum function calculate_max_sum( $a , $n ) { // sorts the array c++ stl sort( $a ); $max_sum = 0; // traverse to find the maximum sum for ( $i = 0; $i < $n / 2; $i ++) { // the farthest distant elements sum // will always be maximum $max_sum += abs ( $a [ $n - 1 - $i ] - $a [ $i ]); } return $max_sum ; } // Driver Code $a = array (10, -10, 20, -40); $n = sizeof( $a ); echo ( "The minimum sum of pairs is " . calculate_min_sum( $a , $n ) . "\n" ); echo ( "The maximum sum of pairs is " . calculate_max_sum( $a , $n )); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript program to find minimum and maximum // sum of absolute differences of pairs // Function to calculate minimum sum function calculate_min_sum(a, n) { // Sorts the array c++ stl a.sort(); // Initially min=0 and max=0 let min_sum = 0; // Traverse to find the minimum sum for (let i = 1; i < n; i += 2) { // The adjacent elements difference // will always be smaller min_sum += Math.abs(a[i] - a[i - 1]); } return min_sum; } // Function to calculate maximum sum function calculate_max_sum(a, n) { // Sorts the array c++ stl a.sort(); let max_sum = 0; // Traverse to find the maximum sum for (let i = 0; i < parseInt(n / 2, 10); i++) { // The farthest distant elements sum // will always be maximum max_sum += Math.abs(a[n - 1 - i] - a[i]); } return max_sum; } // Driver code let a = [ 10, -10, 20, -40 ]; let n = a.length; document.write( "The minimum sum of pairs is " + calculate_min_sum(a, n) + "</br>" ); document.write( "The maximum sum of pairs is " + calculate_max_sum(a, n)); // This code is contributed by decode2207 </script> |
Output
The minimum sum of pairs is 40 The maximum sum of pairs is 80
Time complexity : O(n log n)