हमें पूर्णांक तत्वों की एक सरणी दी गई है और कार्य दिए गए सरणी से उप-अनुक्रम ढूंढना है जिसमें GCD 1 है। GCD दो या अधिक का सबसे बड़ा सामान्य भाजक है पूर्णांक जो दी गई संख्याओं को पूरी तरह से विभाजित करते हैं और सभी के बीच सबसे बड़ा।
इनपुट - int arr[] ={3, 4, 8, 16}
आउटपुट − GCD 1 के साथ उप-अनुक्रमों की संख्या है − 7
स्पष्टीकरण -
जीसीडी के साथ 1 के रूप में दिए गए सरणी से बनने वाले उप-अनुक्रम हैं (3, 4), (3, 8), (3, 16), (4, 3), (8, 3), (16, 3), (3, 4, 8)
इनपुट - int arr[] ={5, 7, 10}
आउटपुट − GCD 1 के साथ उप-अनुक्रमों की संख्या − 3
. हैस्पष्टीकरण -
जीसीडी के साथ 1 के रूप में दिए गए सरणी से बनने वाले उप-अनुक्रम हैं (5, 7), (7, 10), (5, 7, 10)
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
किसी भी आकार के पूर्णांक तत्वों की एक सरणी इनपुट करें।
-
किसी सरणी के आकार की गणना करें और आगे की प्रक्रिया के लिए डेटा को फ़ंक्शन में पास करें
-
GCD के साथ उप-अनुक्रमों की संख्या को 1
. के रूप में संग्रहीत करने के लिए एक अस्थायी चर गणना घोषित करें -
एक सरणी के आकार तक i से 0 तक के लिए लूप प्रारंभ करें
-
लूप के अंदर एक और लूप शुरू करें, जब तक कि एक सरणी के आकार तक j से 0 तक न हो
-
लूप के अंदर, IF GCD(arr[i], arr[j]) =TRUE जांचें, फिर गिनती को 1 तक बढ़ाएं
-
वापसी की संख्या
-
परिणाम प्रिंट करें।
उदाहरण
# include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
if (a == 0)
return b;
return gcd(b % a, a);
}
int GCD_1(int arr[],int size){
int count = 0;
for(int i=0;i<size;i++){
for(int j=0;j<=size;j++){
if(gcd(arr[i],arr[j])==1){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {3, 4, 8, 16};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Count of number of sub-sequences with GCD 1 are: "<<GCD_1(arr, size);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of number of sub-sequences with GCD 1 are: 7
