সমস্যা বিবরণ
আকার n এর একটি অ্যারে "arr" এবং একটি এলিমেন্ট x দেওয়া আছে। অ্যারেতে ন্যূনতম কতগুলো এলিমেন্ট যোগ করলে মেডিয়ান x হবে তা বের করতে হবে।
দৈর্ঘ্য n এর একটি অ্যারেতে মেডিয়ান হল সর্ট করার পর (n-1)/2 পজিশনের এলিমেন্ট। উদাহরণস্বরূপ, নিচের অ্যারেতে মেডিয়ান ২০:
arr1[] = {10, 20, 30, 40}
যদি arr[] = {1, 2, 3} এবং x = 4 হয়, তবে {4, 5, 5, 5} যোগ করলে মেডিয়ান ৪ হবে।
এলগরিদম
এলগরিদম খুব সহজ। মেডিয়ান x না হওয়া পর্যন্ত অ্যারেতে x যোগ করতেই থাকব।
উদাহরণ কোড
#include <iostream>
#include <algorithm>
using namespace std;
int minNumbersToBeAdded(int *arr, int n, int x) {
sort(arr, arr + n);
int cnt = 0;
while (arr[(n - 1)/2] != x) {
arr[n] = x;
++n;
sort(arr, arr + n);
++cnt;
}
return cnt;
}
int main() {
int arr[20] = {1, 2, 3};
int x = 4;
int n = 3;
cout << "Minimum numbers to be added = " << minNumbersToBeAdded(arr, n, x) << endl;
return 0;
}
আউটপুট
প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:
Minimum numbers to be added = 4
