समस्या कथन
N तत्वों का एक ऐरे arr[] और एक पूर्णांक K दिया गया है जहां K < N। कार्य उसी ऐरे में K पूर्णांक तत्व डालना है ताकि परिणामी ऐरे की माध्यिका अधिकतम हो।
यदि इनपुट ऐरे है {1, 3, 2, 5} और k = 3 तो:
- सॉर्टेड ऐरे बन जाता है {1, 2, 3, 5}
- 5 से बड़े 3 तत्व डालें। इस ऑपरेशन के बाद ऐरे बन जाता है {1, 2, 3, 5, 6, 6, 6}
- नए ऐरे की माध्यिका 5 है
एल्गोरिदम
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
