निरपेक्ष अंतर के न्यूनतम योग के साथ ऐरे तत्व?

यहां हम एक दिलचस्प समस्या देखेंगे। हम एन तत्वों के साथ एक सरणी 'ए' ले रहे हैं। हमें एक ऐसा अवयव x ज्ञात करना है कि |a[0] - x| + |a[1] - x|+ … + |a[n-1] - x| न्यूनीकृत किया जाता है। फिर हमें न्यूनतम राशि ज्ञात करनी होगी।

मान लीजिए सरणी है:{1, 3, 9, 6, 3} अब x 3 है। तो योग है |1 - 3| + |3 - 3| + |9 - 3| + |6 - 3| + |3 - 3| =11.

इस समस्या को हल करने के लिए, हमें सरणी की माध्यिका को x के रूप में चुनना होगा। यदि सरणी का आकार सम है, तो दो माध्य मान होंगे। ये दोनों ही x का इष्टतम विकल्प होंगे।

एल्गोरिदम

न्यूनतम राशि(गिरफ्तारी, एन)

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

उदाहरण

#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);
}

आउटपुट

Sum : 11