এই প্রোগ্রামটি অ্যারেতে এমন একটি উপাদান খুঁজে বের করে যেটার সাথে বাকি সব উপাদানের এবসোলিউট ডিফারেন্সের যোগফল ন্যূনতম।
প্রয়োজনীয় ধারণা
- অ্যারে (Array) — একই টাইপের উপাদানগুলোর সংগ্রহ, দৈর্ঘ্য পূর্বনির্ধারিত।
- এবসোলিউট ডিফারেন্স (Absolute Difference) — দুটি সংখ্যার পার্থক্যের ধনাত্মক মান (নেগেটিভ হলে পজিটিভে কনভার্ট)।
সূত্র: Minimum Absolute Difference (a) = min(abs(a – arr[j])); যেখানে 1 ≤ j ≤ n এবং j ≠ i।
উদাহরণ
Input: arr = {1, 3, 9, 3, 6} Output: 8
ব্যাখ্যা
অপ্টিমাল সমাধান: x = 3 বেছে নিলে যোগফল = |1–3| + |3–3| + |9–3| + |3–3| = 2 + 0 + 6 + 0 = 8।
অ্যালগরিদম
- অ্যারে সর্ট করুন।
- প্রথম উপাদানের জন্য দ্বিতীয় উপাদান দিয়ে ডিফারেন্স।
- শেষ উপাদানের জন্য শেষ থেকে দ্বিতীয় উপাদান দিয়ে ডিফারেন্স।
- মাঝপথের উপাদানগুলোর জন্য:
minAbsDiff = min(abs(arr[i]–arr[i-1]), abs(arr[i]–arr[i+1]))। - সব যোগফল করুন।
C++ কোড উদাহরণ
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a[] = {1, 3, 9, 3, 6};
int n = 5;
sort(a, a + n);
int sum = 0;
sum += abs(a[0] - a[1]);
sum += abs(a[n-1] - a[n-2]);
for (int i = 1; i < n-1; i++) {
sum += min(abs(a[i] - a[i-1]), abs(a[i] - a[i+1]));
}
cout << "The element with minimum sum of absolute differences is : " << sum;
return 0;
}
আউটপুট
The element with minimum sum of absolute differences is : 8
