C++ में उन उपसमुच्चयों की संख्या गिनें जिनका माध्यिका उसी उपसमुच्चय में मौजूद है

समस्या विवरण

एक सरणी arr[] दी गई है जिसमें धनात्मक संख्याएं हैं। लक्ष्य arr[] के तत्वों के उपसमुच्चय ढूंढना है जैसे कि उपसमुच्चय के मानों की माध्यिका भी उसी सेट में मौजूद हो।

उदाहरण

इनपुट

arr[] = { 1,2,3 }

आउटपुट

उपसमुच्चयों की संख्या: 4

व्याख्या

माध्यिका वाले सेट: [1], माध्यिका 1; [2], माध्यिका 2; [3], माध्यिका 3; [1,2,3], माध्यिका 2

इनपुट

arr[] = { 4,6,5 }

आउटपुट

उपसमुच्चयों की संख्या: 4

व्याख्या

माध्यिका वाले सेट: [4], [6], [5], [4,6,5]

दृष्टिकोण

इस दृष्टिकोण में हम सम और विषम आकार के तत्वों की जांच करेंगे। फिर हम इस तथ्य के आधार पर माध्यिका ढूंढ सकते हैं कि विषम संख्या में आइटम के लिए, माध्यिका मध्य तत्व के रूप में उसी सेट में मौजूद होती है। इसलिए हम गिनती में 2^(n-1) जोड़ेंगे। सम लंबाई के उपसमुच्चयों के लिए हम जांचेंगे कि क्या दो समान तत्व हैं, तो दो मध्य तत्वों वाले सम लंबाई के उपसमुच्चयों के लिए गिनती करेंगे।

एल्गोरिदम चरण

• धनात्मक संख्याओं की सरणी arr[] लें।
• फंक्शन median_subset(arr, size) arr लेता है और उन उपसमुच्चयों की संख्या लौटाता है जिनकी माध्यिका उसी उपसमुच्चय में मौजूद है।
• फंक्शन check(int temp) एक पूर्णांक लेता है और for लूप का उपयोग करके i=2 से i<=temp तक उस संख्या का फैक्टोरियल लौटाता है।
• count = count * i की गणना करें, और लूप के अंत में इसे फैक्टोरियल के रूप में लौटाएं।
• फंक्शन com(int n, int r) n और r लेता है और संयोजन nCr का मान लौटाता है। इसमें temp = check(r) * check(n - r) और temp_2 = check(n) / temp लें। गणना किए गए मान के रूप में temp_2 लौटाएं।
• फंक्शन power(int n, int r) n और r लेता है और n^r का मान लौटाता है।
• यदि r 0 है तो उत्तर 1 होगा इसलिए 1 लौटाएं।
• total = power(n, r / 2) लें। (n^(r/2))
• total को total^2 % mod से अपडेट करें। जहां mod=1000000007।
• यदि r सम है तो temp लौटाएं (total * n) % mod के रूप में, अन्यथा total लौटाएं।
• फंक्शन median_subset() के अंदर, count = power(2, size - 1) लें जो विषम लंबाई के उपसमुच्चयों की संख्या है।
• sort(arr, arr + size) का उपयोग करके सरणी arr[] को सॉर्ट करें।
• while लूप का उपयोग करके हम प्रत्येक तत्व के लिए बाएं मध्य तत्व की जांच करेंगे जब तक वे बराबर हैं।
• temp_2 = size - 1 - temp लें दाएं मध्य तत्व के दाएं तत्वों की संख्या के रूप में।
• temp_3 = i लें बाएं मध्य तत्व के बाएं तत्वों की संख्या के रूप में।
• चयनित सम लंबाई के उपसमुच्चयों को गिनती में जोड़ें: count = (count + com(temp_3 + temp_2, temp_3)) % mod।
• while लूप के अंत में हमारे पास गिनती होगी।
• परिणाम के रूप में गिनती लौटाएं।

C++ कोड उदाहरण

#include <algorithm>
#include <iostream>
using namespace std;
#define MOD 1000000007

int check(int temp) {
    int count = 1;
    for (int i = 2; i <= temp; i++) {
        count = count * i;
    }
    return count;
}

int com(int n, int r) {
    int temp = check(r) * check(n - r);
    int temp_2 = check(n) / temp;
    return temp_2;
}

int power(int n, int r) {
    if (r == 0) {
        return 1;
    }
    int total = power(n, r / 2);
    total = (total * total) % MOD;
    if (r % 2) {
        int temp = (total * n) % MOD;
        return temp;
    } else {
        return total;
    }
}

int median_subset(int* arr, int size) {
    int count = power(2, size - 1);
    sort(arr, arr + size);
    for (int i = 0; i < size; ++i) {
        int temp = i + 1;
        while (temp < size && arr[temp] == arr[i]) {
            int temp_2 = size - 1 - temp;
            int temp_3 = i;
            count = (count + com(temp_3 + temp_2, temp_3)) % MOD;
            temp++;
        }
    }
    return count;
}

int main() {
    int arr[] = { 4, 5, 4, 6 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "उपसमुच्चयों की संख्या: " << median_subset(arr, size);
    return 0;
}

आउटपुट

उपसमुच्चयों की संख्या: 9