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

यहां हम एक दिलचस्प समस्या देखेंगे। हम 'a' नामक N तत्वों वाला एक ऐरे ले रहे हैं। हमें एक तत्व 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 का इष्टतम विकल्प होगा।

एल्गोरिदम

minSum(arr, n)

शुरुआत
    ऐरे arr को सॉर्ट करें
    sum := 0
    med := arr की माध्यिका
    arr में प्रत्येक तत्व e के लिए करें
        sum := sum + |e - med|
    पूर्ण
    sum वापस करें
समाप्त

उदाहरण

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

आउटपुट

Sum: 11