Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Webinars
About Us

Edit
Reply




Edit

Finding the Sum of Minimum Absolute Difference of the given Array

Published on 10 Mar 2020

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 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
C++
Java
Python 3

Output
Enter the number of elements : 5
Input the array elements : 1 3 9 6 3
The minimum sum of absolute is : 11

Time complexity: O(n)


Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in