C++ में दिए गए GCD के बराबर उपसमुच्चयों की संख्या गिनें

समस्या विवरण

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

उदाहरण

इनपुट

arr[] = {10, 5, 6, 3}, GCD[] = {2, 3, 5}

आउटपुट

दिए गए GCD के बराबर उपसमुच्चयों की संख्या: 1 2 2

व्याख्या

GCD 2 के बराबर उपसमुच्चय: [10, 6]। GCD 3 के बराबर उपसमुच्चय: [3], [6,3]। GCD 5 के बराबर उपसमुच्चय: [5], [10, 5]

इनपुट

arr[] = {10, 21, 7, 8}, GCD[] = {2, 7, 5}

आउटपुट

दिए गए GCD के बराबर उपसमुच्चयों की संख्या: 1 2 0

व्याख्या

GCD 2 के बराबर उपसमुच्चय: [10, 8]। GCD 7 के बराबर उपसमुच्चय: [7], [21,7]। GCD 5 के बराबर कोई उपसमुच्चय नहीं।

दृष्टिकोण

इस दृष्टिकोण में हम एक unordered_map<int, int> um_1 बनाएंगे arr[] के तत्वों की फ्रीक्वेंसी संग्रहीत करने के लिए और इसी तरह का मैप um_2 दिए गए GCD के साथ उपसमुच्चयों की संख्या संग्रहीत करने के लिए। arr[] के तत्वों में अधिकतम मान लें count के रूप में। अब i=count से i>=1 तक लूप चलाएं और वर्तमान GCD के लिए उपसमुच्चयों की संख्या ढूंढें। इसके लिए हम um_1 में i के गुणकों की संख्या गिनेंगे। यदि i के गुणकों की संख्या total है तो GCD i वाले उपसमुच्चयों की संख्या 2^total - 1 - temp होगी। जहां temp उन उपसमुच्चयों की संख्या है जिनका GCD i से बड़ा है लेकिन i के बराबर नहीं है।

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

arr[] और GCD[] के लिए दो सरणियां लें।
फंक्शन subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD) दोनों सरणियों और उनकी लंबाई लेता है और दिए गए GCD के बराबर उपसमुच्चयों की संख्या लौटाता है।
प्रारंभिक गिनती 0 लें।
for लूप का उपयोग करके arr[] को पार करें और अधिकतम मान के रूप में count ढूंढें और um_1[arr[i]]++ का उपयोग करके फ्रीक्वेंसी अपडेट करें।
for लूप का उपयोग करके i=count से i>=1 तक, total को i के गुणकों की फ्रीक्वेंसी के योग के रूप में लें और temp=0 उन उपसमुच्चयों की संख्या के रूप में जिनका GCD i से बड़ा है लेकिन i के बराबर नहीं है।
फिर से j=2 से j*i <= count तक पार करें, um_1[j*i] को total में जोड़ें और um_2[j*i] को temp में जोड़ें।
दोनों लूप के अंत में um_2[i] = (1 << total) - 1 - temp सेट करें।
परिणामी सरणी के लिए um_2[GCD[i]] प्रिंट करें जिसमें दिए गए GCD वाले उपसमुच्चयों की संख्या है।

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

#include <bits/stdc++.h>
using namespace std;

void subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD) {
    unordered_map<int, int> um_1, um_2;
    int count = 0;
    for (int i=0; i<size_arr; i++) {
        count = max(count, arr[i]);
        um_1[arr[i]]++;
    }
    for (int i = count; i >=1; i--) {
        int temp = 0;
        int total = um_1[i];
        for (int j = 2; j*i <= count; j++) {
            total += um_1[j*i];
            temp += um_2[j*i];
        }
        um_2[i] = (1<<total) - 1 - temp;
    }
    cout << "दिए गए GCD के बराबर उपसमुच्चयों की संख्या: ";
    for (int i=0; i<size_GCD; i++) {
        cout << um_2[GCD[i]] << " ";
    }
}

int main() {
    int GCD[] = {2, 3};
    int arr[] = {9, 6, 2};
    int size_arr = sizeof(arr)/sizeof(arr[0]);
    int size_GCD = sizeof(GCD)/sizeof(GCD[0]);
    subset_GCD(arr, size_arr, GCD, size_GCD);
    return 0;
}

आउटपुट

दिए गए GCD के बराबर उपसमुच्चयों की संख्या: 2 1