সমস্যা বিবরণ
N উপাদানের একটি অ্যারে arr[] এবং একটি ইন্টিজার K দেওয়া আছে যেখানে K < N। কাজ হল একই অ্যারেতে Kটি ইন্টিজার উপাদান যোগ করা যাতে ফলাফলস্বরূপ অ্যারের মেডিয়ান সর্বাধিক হয়।
যদি ইনপুট অ্যারে হয় {1, 3, 2, 5} এবং k = 3 তবে:
- সর্টেড অ্যারে হয় {1, 2, 3, 5}
- ৫ থেকে বড় ৩টি উপাদান যোগ করুন। এই অপারেশনের পর অ্যারে হয় {1, 2, 3, 5, 6, 6, 6}
- নতুন অ্যারের মেডিয়ান হল ৫
অ্যালগরিদম
1. ফলাফলস্বরূপ অ্যারের মেডিয়ান সর্বাধিক করার জন্য, যোগ করা যাবতীয় সব উপাদান অবশ্যই অ্যারের সর্বোচ্চ উপাদানের চেয়ে বড় হতে হবে। 2. অ্যারেটি সর্ট করুন এবং অ্যারের মেডিয়ান হবে arr[size/2] যদি সাইজ বিজোড় হয়, অন্যথায় (arr[(size/2)-1] + arr[size/2]) / 2।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
double getMaxMedian(int* arr, int n, int k) {
int newSize = n + k;
double median;
sort(arr, arr + n);
if (newSize % 2 == 0) {
median = (arr[(newSize / 2) - 1] + arr[newSize / 2]) / 2;
return median;
}
median = arr[newSize / 2];
return median;
}
int main() {
int arr[] = {1, 3, 2, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "Max median = " << getMaxMedian(arr, n, k) << endl;
return 0;
}
আউটপুট
Max median = 5
