Given an array arr[] ( 1-based indexing ) consisting of N integers, the task is to find the minimum sum of the absolute difference between all pairs of array elements by decrementing and incrementing any pair of elements by 1 any number of times.
Examples:
Input: arr[] = {1, 2, 3}
Output: 0
Explanation:
Modify the array elements by performing the following operations:
- Choose the pairs of element (arr[1], arr[3]) and incrementing and decrementing the pairs modifies the array to {2, 2, 2}.
After the above operations, the sum of the absolute differences is |2 – 2| + |2 – 2| + |2 – 2| = 0. Therefore, print 0.
Input: arr[] = {0, 1, 0, 1}
Output: 4
Approach: The given problem can be solved by using a Greedy Approach. It can be observed that to minimize the sum of the absolute difference between every pair of array elements arr[], the idea to make every array element closed to each other. Follow the steps below to solve the problem:
- Find the sum of the array elements arr[] and store it in a variable, say sum.
- Now, if the value of sum % N is 0, then print 0 as all the array elements can be made equal and the resultant value of the expression is always 0. Otherwise, find the value of sum % N and store it in a variable, say R.
- Now, if all the array elements are sum/N, then we can make R number of array elements as 1 and the rest of the array elements as 0 to minimize the resultant value.
- After the above steps, the minimum sum of the absolute difference is given by R*(N – R).
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum value// of the sum of absolute difference// between all pairs of arraysint minSumDifference(int ar[], int n){ // Stores the sum of array elements int sum = 0; // Find the sum of array element for (int i = 0; i < n; i++) sum += ar[i]; // Store the value of sum%N int rem = sum % n; // Return the resultant value return rem * (n - rem);}// Driver Codeint main(){ int arr[] = { 3, 6, 8, 5, 2, 1, 11, 7, 10, 4 }; int N = sizeof(arr) / sizeof(int); cout << minSumDifference(arr, N); return 0;} |
Java
// Java program for the above approachclass GFG { // Function to find the minimum value // of the sum of absolute difference // between all pairs of arrays public static int minSumDifference(int ar[], int n) { // Stores the sum of array elements int sum = 0; // Find the sum of array element for (int i = 0; i < n; i++) sum += ar[i]; // Store the value of sum%N int rem = sum % n; // Return the resultant value return rem * (n - rem); } // Driver Code public static void main(String args[]) { int[] arr = { 3, 6, 8, 5, 2, 1, 11, 7, 10, 4 }; int N = arr.length; System.out.println(minSumDifference(arr, N)); }}// This code is contributed by gfgking. |
Python3
# Python 3 program for the above approach# Function to find the minimum value# of the sum of absolute difference# between all pairs of arraysdef minSumDifference(ar, n): # Stores the sum of array elements sum = 0 # Find the sum of array element for i in range(n): sum += ar[i] # Store the value of sum%N rem = sum % n # Return the resultant value return rem * (n - rem)# Driver Codeif __name__ == '__main__': arr = [3, 6, 8, 5, 2, 1, 11, 7, 10, 4] N = len(arr) print(minSumDifference(arr, N)) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;class GFG{// Function to find the minimum value// of the sum of absolute difference// between all pairs of arrayspublic static int minSumDifference(int[] ar, int n) { // Stores the sum of array elements int sum = 0; // Find the sum of array element for(int i = 0; i < n; i++) sum += ar[i]; // Store the value of sum%N int rem = sum % n; // Return the resultant value return rem * (n - rem);}// Driver Codepublic static void Main(){ int[] arr = { 3, 6, 8, 5, 2, 1, 11, 7, 10, 4 }; int N = arr.Length; Console.Write(minSumDifference(arr, N));}}// This code is contributed by sanjoy_62 |
Javascript
<script>// JavaScript program for the above approach// Function to find the minimum value// of the sum of absolute difference// between all pairs of arraysfunction minSumDifference(ar, n) { // Stores the sum of array elements let sum = 0; // Find the sum of array element for (let i = 0; i < n; i++) sum += ar[i]; // Store the value of sum%N let rem = sum % n; // Return the resultant value return rem * (n - rem);}// Driver Codelet arr = [3, 6, 8, 5, 2, 1, 11, 7, 10, 4];let N = arr.length;document.write(minSumDifference(arr, N));</script> |
Output:
21
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
