एक सरणी ar को देखते हुए, जिसमें धनात्मक संख्याएँ होती हैं और एक सरणी GCD[] जिसमें gcd मान होते हैं। लक्ष्य arr[] के तत्वों के सबसेट की संख्या का पता लगाना है जिसमें GCD में दिए गए gcd मान हैं []।
उदाहरण के लिए
इनपुट
arr[] = {10, 5, 6, 3}, GCD[] = {2, 3, 5} आउटपुट
Count of number of subsets of a set with GCD equal to a given number are: 1 2 2
स्पष्टीकरण
The subsets with GCD equal to 2 is [ 10, 6 ]. Subsets with GCD equal to 3 is [ 3 ], [ 6,3 ] Subsets with GCD equal to 5 is [ 5 ], [ 10, 5 ]
इनपुट
arr[] = {10, 21, 7, 8}, GCD[] = {2, 7, 5} आउटपुट
Count of number of subsets of a set with GCD equal to a given number are: 1 2 0
स्पष्टीकरण
The subsets with GCD equal to 2 is [ 10, 8 ]. Subsets with GCD equal to 7 is [ 7 ], [ 21,7 ] There are no subsets with GCD equal to 5.
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
इस दृष्टिकोण में हम arr के तत्वों की आवृत्तियों को संग्रहीत करने के लिए एक unordered_map
-
एआर [] और जीसीडी [] के लिए दो सरणियाँ लें।
-
फ़ंक्शन सबसेट_जीसीडी(int arr[], int size_arr, int GCD[], int size_GCD) सरणियों और उनकी लंबाई दोनों को लेता है और किसी दिए गए नंबर के बराबर GCD वाले सेट के सबसेट की संख्या की गणना देता है।
-
फ़ंक्शन सबसेट_जीसीडी(int arr[], int size_arr, int GCD[], int size_GCD) सरणियों और उनकी लंबाई दोनों को लेता है और किसी दिए गए नंबर के बराबर GCD वाले सेट के सबसेट की संख्या की गणना देता है।
-
प्रारंभिक गणना 0 के रूप में लें।
-
ट्रैवर्स एआर [] लूप के लिए उपयोग कर रहा है और अद्यतन गणना को अधिकतम मान के रूप में ढूंढें और um_1 को um_1[arr[i]]++ का उपयोग करके आवृत्तियों के साथ अपडेट करें।
-
i=गिनती से i>=1 के लिए लूप का उपयोग करते हुए, कुल को i और temp=0 के गुणकों की बारंबारता के योग के रूप में लें, उन उपसमुच्चयों की संख्या के रूप में जिनके पास gcd i से अधिक है लेकिन i के बराबर नहीं है।
-
j=2 से j*i<=count तक फिर से ट्रैवर्स करें, um_1[j*i] को टोटल में जोड़ें और um_2[j*i] को टेम्परेचर में जोड़ें।
-
लूप के लिए दोनों के अंत के बाद um_2[i] =(1<<कुल) - 1 - अस्थायी सेट करें।
-
परिणामी सरणी के लिए um_2[GCD[i]] प्रिंट करें जिसमें GCD के साथ सबसेट की संख्या दी गई हो।
उदाहरण
#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<<"Count of number of subsets of a set with GCD equal to a given number are: ";
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;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of number of subsets of a set with GCD equal to a given number are: 2 1