समस्या कथन
आकार n और तत्व x की एक सरणी "गिरफ्तारी" को देखते हुए, कार्य औसत को x के बराबर बनाने के लिए सरणी में जोड़े जाने वाले तत्वों की न्यूनतम संख्या को खोजना है।
n की लंबाई के साथ एक सरणी में एक माध्यिका एक तत्व है जो गैर-घटते क्रम में तत्वों को क्रमबद्ध करने के बाद स्थिति संख्या (n-1) / 2 पर कब्जा कर लेता है। उदाहरण के लिए, नीचे सरणी में माध्यिका 20 है -
arr1[] ={10, 20, 30, 40}
अगर arr[] ={1, 2, 3} और x =4 तो हमें 4 के बराबर माध्य बनाने के लिए सरणी में 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