সি-তে ন্যূনতম निरপেক্ষ পার্থক্য যোগফল দেনে অ্যারে উপাদান

একটি অ্যারে '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।

সমাধান: অ্যারেটি সর্ট করে মিডিয়ান বের করুন। যদি আকার জোড় হয় তবে দুটি মিডিয়ান যেকোনো একটি বেছে নেওয়া যায়।

অ্যালগরিদম

minSum(arr, n)

begin sort arr sum := 0 med := median of arr for each 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