Given an array arr[] consisting of N integers, the task is to find the minimum sum of all absolute differences between unique pairs of elements in the array after updating the array arr[]. To update the array, any two elements from the array can be chosen in any order. 1 is subtracted from the first element and added to the second element. This step can be repeated any number of times.
Examples:
Input: arr[]={1, 2, 3}
Output: 0
Explanation: Choosing 1 and 3 for updating the array, 3-1=2 and 1+1=2. So the updated array becomes arr[]={2, 2, 2}. Minimum possible sum of the absolute difference of pairs is 0+0+0=0.Input: arr[]={0, 1, 1, 0}
Output: 4
Explanation: Choosing any two elements for updation will lead to increase in total sum of absolute differences. So the sum is 1+1+1+1+0+0=4.
Approach: The given problem can be solved based on the following observations:
- To minimize the sum of absolute differences between all the unique pairs, the elements should be as closest as possible.
- To make that, find the sum S and divide sum S by N i.e, val = S/N.
- If val is an integer, then the problem becomes very simple as following the operations all the integers can be converted to X.
- Else, some elements say X will be the integer just less than val, i.e, floor(val) and others will be ceil(val).
- For finding the value of X, use the fact that even after updating the sum of the array will be same. So, use the following equation to find the value of X.
x*(b-1) + N*b – x*b = S
=> x*b – x + N*b – x*b = S
=> N*b – x = S
=> x = N*b – S
- For e.g.
N = 10
arr[] = {8, 3, 6, 11, 5, 2, 1, 7, 10, 4}
Sum of all elements of the array, S=57
So, S/N = 5.7 means if all the elements are converted to 5.7, then the sum of all absolute differences b/w all unique pairs of elements will be minimized i.e, 0.
But converting all elements to 5.7 using the mentioned operation isn’t possible.
So, some elements will be 5 and the others will be 6.Now, the question is how many elements will be 5. Let’s say x, then (N-x) will be 6 and in all this process sum will be always be conserved.
=> x*5 + (N-x)*6 = 57
=> -x = 57 – 60 (Putting the value of N as 10 and solving the equation)
-x = -3 => x=3
So, the converted array will be {5, 5, 5, 6, 6, 6, 6, 6, 6, 6}
- Now the pairs which will give a difference like 1 are x*(N-x).
- So the total sum of differences will also be x*(N-x).
Follow the steps below to solve the problem:
- Initialize the variable sum as 0 to store the sum of elements in the array arr[].
- Iterate over the range [0, N] using the variable i and perform the following steps:
- Add the value of arr[i] in the variable sum.
- Initialize the variable temp as (float)S/N.
- Set the value of a as the floor value of temp.
- Set the value of b as the ceil value of temp.
- Set the value of x as b*N-sum to store the position where partition will happen.
- Print the value of x*(N-x) as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the minimum// sum of differences of pairsvoid solve(int N, int arr[]){ int a, b, S = 0, x; for (int i = 0; i < N; i++) { // Take sum of all elements S = S + arr[i]; } // Store s/n to a temporary float // variable and typecast // s/n to get exact float value float temp = (float)S / N; // take floor value of temp a = floor(temp); // take floor value of temp b = ceil(temp); // position where partition will happen x = b * N - S; // Total sum of differences cout << x * (N - x);}// Driver Codeint main(){ int arr[] = { 8, 3, 6, 11, 5, 2, 1, 7, 10, 4 }; int N = sizeof(arr) / sizeof(arr[0]); solve(N, arr); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to calculate the minimum// sum of differences of pairsstatic void solve(int N, int arr[]){ int a, b, S = 0, x; for (int i = 0; i < N; i++) { // Take sum of all elements S = S + arr[i]; } // Store s/n to a temporary float // variable and typecast // s/n to get exact float value float temp =(float) S / N; // take floor value of temp a = (int) Math.floor(temp); // take floor value of temp b = (int)Math.ceil(temp); // position where partition will happen x = b * N - S; // Total sum of differences System.out.println(x * (N - x));}// Driver Code public static void main (String[] args) { int arr[] = { 8, 3, 6, 11, 5, 2, 1, 7, 10, 4 }; int N = arr.length; solve(N, arr); }}// This code is contributed by Potta Lokesh |
Python3
# Python program for the above approachimport math# Function to calculate the minimum# sum of differences of pairsdef solve(N, arr): a, b, S, x = 0, 0, 0, 0; for i in range(0, N, 1): # Take sum of all elements S = S + arr[i]; # Store s/n to a temporary float # variable and typecast # s/n to get exact float value temp = S / N; # take floor value of temp a = math.floor(temp); # take floor value of temp b = math.ceil(temp); # position where partition will happen x = b * N - S; # Total sum of differences print(x * (N - x));# Driver Codeif __name__ == '__main__': arr = [ 8, 3, 6, 11, 5, 2, 1, 7, 10, 4 ]; N = len(arr); solve(N, arr);# This code is contributed by 29AjayKumar |
C#
using System;public class GFG { static void solve(int N, int[] arr) { int b, S = 0, x; for (int i = 0; i < N; i++) { // Take sum of all elements S = S + arr[i]; } // Store s/n to a temporary float // variable and typecast // s/n to get exact float value float temp = (float)S / N; // take floor value of temp b = (int)Math.Ceiling(temp); // position where partition will happen x = b * N - S; // Total sum of differences Console.WriteLine(x * (N - x)); } // Driver Code static public void Main() { int[] arr = { 8, 3, 6, 11, 5, 2, 1, 7, 10, 4 }; int N = arr.Length; solve(N, arr); }}// This code is contributed by maddler. |
Javascript
<script>// javascript program for the above approach// Function to calculate the minimum// sum of differences of pairsfunction solve(N, arr) { let a, b, S = 0, x; for (let i = 0; i < N; i++) { // Take sum of all elements S = S + arr[i]; } // Store s/n to a temporary float // variable and typecast // s/n to get exact float value let temp = S / N; // take floor value of temp a = Math.floor(temp); // take floor value of temp b = Math.ceil(temp); // position where partition will happen x = b * N - S; // Total sum of differences document.write(x * (N - x));}// Driver Codelet arr = [8, 3, 6, 11, 5, 2, 1, 7, 10, 4];let N = arr.length;solve(N, arr);// This code is contributed by gfgking.</script> |
21
Time Complexity : O(N)
Auxiliary Space : O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
