Find the sum of minimum absolute difference of the given array

Program to find the sum of minimum absolute difference of the array is discussed here. An array of distinct elements is given as input and the sum of minimum absolute difference of each array element has to be found. The minimum absolute difference is calculated using the formula,

Minimum Absolute Difference (a) = min(abs(a – arr[j])) ; where 1 <= j <= n and j != i, abs is the absolute value.

For example, consider the following array given as input: arr = {1, 3, 9, 3, 6}

The optimal solution is to choose x = 3, which produces the sum
|1 – 3| + |3 – 3| + |9 – 3| + |3 – 3| + |6 – 3| = 2 + 0 + 6 + 0 + 3 = 11

Output : 11

Algorithm

  • The given input array is sorted.
  • For the first element of the array, its minimum absolute difference is calculated using the second array element.
  • For the last array element, its minimum absolute difference is calculated using the second last array element.
  • For the other array elements, minimum absolute difference for an element at index i is calculated as follow:
  • minAbsDiff = min( abs(arr[i] – arr[i-1]), abs(ar[i] – arr[i+1]) ).

Program to find the sum of minimum absolute difference of the given array

// C program to find the sum of minimum absolute difference of the array

#include
#include
int min(int a, int b)
{
if(a>b)
return b;
else
return a;
}

// Function to find absolute sum
int abs_sum(int arr[], int n)
{

int sum = 0;

sum += abs(arr[0] – arr[1]); 
sum += abs(arr[n-1] – arr[n-2]);

for (int i=1; i<n-1; i++)
sum += min(abs(arr[i] – arr[i-1]), abs(arr[i] – arr[i+1]));  // Total sum of absolute difference

return sum;
}

// Function to sort the elements

void sort(int a[], int n)
{
for(int i = 0; i < n-1; i++)
{
for(int j = 0; j < n-i-1; j++)
{
if (a[j] > a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}}}}

int main()
{
int a[20], n, i;
scanf(“%d”, &n);
for(i=0; i<n; i++)
{
scanf(“%d”, &a[i]);
}
sort(a, n);
printf(“The minimum sum of absolute is %d”,abs_sum(a, n));
return 0;
}

// C++ program to find the sum of minimum absolute difference of the given array

#include <bits/stdc++.h>
using namespace std;
int abs_sum(int a[], int len);
int main()
{
int a[20], n, i;
cout << “\nEnter the number of elements : “;
cin >> n;
cout << “\nInput the array elements : “;
for(i=0; i<n; i++)
{
cin >> a[i];
}
cout << “\nThe sum of minimum absolute differences : ” << abs_sum(a, n) << endl;
return 0;
}

// Function to calculate absolute sum 
int abs_sum(int arr[], int n)
{
sort(arr, arr+n);

int sum = 0;

sum += abs(arr[0] – arr[1]);
sum += abs(arr[n-1] – arr[n-2]);

for (int i=1; i<n-1; i++)
sum += min(abs(arr[i] – arr[i-1]), abs(arr[i] – arr[i+1]));  // Total sum of absolute differences

return sum;
}

// Java program to find the sum of minimum absolute difference in an array

import java.*;
import java.util.Arrays;

public class Main
{
static int sumOfMinAbsDifferences(
int arr[] ,int n)
{

Arrays.sort(arr);
int sum = 0;
sum += Math.abs(arr[0] – arr[1]);
sum += Math.abs(arr[n-1] – arr[n-2]);

for (int i = 1; i < n – 1; i++)
sum +=
Math.min(Math.abs(arr[i] – arr[i-1]),
Math.abs(arr[i] – arr[i+1])); // Total sum of minimum absolute difference

return sum;
}

public static void main(String args[])
{
int arr[] = {1, 3, 6, 9, 3};
int n = arr.length;

System.out.println( “Sum = ” + sumOfMinAbsDifferences(arr, n));
}
}

# Python program to find the sum of minimum absolute differences in an array

def sumOfMinAbsDifferences(arr,n):
arr.sort()
sum = 0

sum += abs(arr[0] – arr[1]);
sum += abs(arr[n – 1] – arr[n – 2]);

for i in range(1, n – 1):
sum += min(abs(arr[i] – arr[i – 1]),
abs(arr[i] – arr[i + 1]))  // Total sum of minimum absolute difference

return sum;

arr = [1,2,3,4,5]
n = len(arr)
print( “Sum = “, sumOfMinAbsDifferences(arr, n))

 

Output:

sum of minimum absolute difference

Time complexity: O(n)