C++ में माध्यिका को x के बराबर बनाने के लिए जोड़े जाने वाले न्यूनतम तत्व

समस्या कथन

आकार n की एक सरणी "arr" और तत्व x दिया गया है, सरणी में जोड़े जाने वाले न्यूनतम तत्वों की संख्या ढूंढें ताकि माध्यिका (median) x के बराबर हो जाए।

लंबाई n की सरणी में माध्यिका वह तत्व है जो तत्वों को गैर-घटते क्रम में सॉर्ट करने के बाद स्थिति (n-1)/2 पर आता है। उदाहरण के लिए, नीचे दी गई सरणी में माध्यिका 20 है: arr1[] = {10, 20, 30, 40}

यदि arr[] = {1, 2, 3} और x = 4, तो हमें सरणी में 4 संख्याएं यानी {4, 5, 5, 5} जोड़नी होंगी ताकि माध्यिका 4 के बराबर हो जाए।

एल्गोरिदम

एल्गोरिदम बहुत सरल है। हमें सरणी में तब तक एक संख्या x जोड़नी है जब तक सरणी की माध्यिका x के बराबर न हो जाए।

C++ उदाहरण

#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, n = 3;
    cout << "Minimum numbers to be added = " << minNumbersToBeAdded(arr, n, x) << endl;
    return 0;
}

आउटपुट

Minimum numbers to be added = 4