Which array element has the smallest sum of absolute differences?

Here, we will see an interesting question. We have an array 'a' containing N elements. We need to find an element x that minimizes the value of |a[0] - x| |a[1] - x| ... |a[n-1] - x|. Then we need to find the minimized sum.

Suppose the array is: {1, 3, 9, 6, 3}, and now x is 3. So the sum is |1 - 3| |3 - 3| |9 - 3| |6 - 3| |3 - 3| = 11.

To solve this problem, we need to choose the median of the array as x. If the size of the array is even, there will be two median values. They are all the best choices for x.

Algorithm

minSum(arr, n)

begin
   sort array arr
   sum := 0
   med := median of arr
   for each element e in arr, do
      sum := sum + |e - med|
   done
   return sum
end

Example

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int minSum(int arr[], int n){
   sort(arr, arr + n);
   int sum = 0;
   int med = arr[n/2];
   for(int i = 0; i<n; i++){
      sum += abs(arr[i] - med);
   }
   return sum;
}
int main() {
   int arr[5] = {1, 3, 9, 6, 3};
   int n = 5;
   cout << "Sum : " << minSum(arr, n);
}

Output

Sum : 11

The above is the detailed content of Which array element has the smallest sum of absolute differences?. For more information, please follow other related articles on the PHP Chinese website!