C++ में GCD 1 वाले सबसीक्वेंस की गणना

हमें पूर्णांक तत्वों की एक सरणी दी गई है और कार्य दिए गए सरणी से उन सबसीक्वेंस को खोजना है जिनका GCD 1 है। GCD दो या अधिक पूर्णांकों का महत्तम समापवर्तक है जो दी गई संख्याओं को पूरी तरह से विभाजित करता है और उनमें सबसे बड़ा होता है।

इनपुट - int arr[] = {3, 4, 8, 16}

आउटपुट - GCD 1 वाले सबसीक्वेंस की संख्या - 7

व्याख्या -

दिए गए सरणी से GCD 1 के साथ बनने वाले सबसीक्वेंस हैं: (3, 4), (3, 8), (3, 16), (4, 3), (8, 3), (16, 3), (3, 4, 8)

इनपुट - int arr[] = {5, 7, 10}

आउटपुट - GCD 1 वाले सबसीक्वेंस की संख्या - 3

व्याख्या -

दिए गए सरणी से GCD 1 के साथ बनने वाले सबसीक्वेंस हैं: (5, 7), (7, 10), (5, 7, 10)

उपयोग किया गया दृष्टिकोण

• किसी भी दिए गए आकार की पूर्णांक तत्वों की सरणी इनपुट करें।
• सरणी का आकार गणना करें और डेटा को आगे की प्रक्रिया के लिए फ़ंक्शन में पास करें
• GCD 1 वाले सबसीक्वेंस की संख्या संग्रहीत करने के लिए एक अस्थायी चर count घोषित करें
• i से 0 से सरणी के आकार तक लूप FOR शुरू करें
• लूप के अंदर j से 0 से सरणी के आकार तक एक और लूप FOR शुरू करें
• लूप के अंदर, जांचें IF GCD(arr[i], arr[j]) = TRUE तो count को 1 से बढ़ाएं
• count लौटाएं
• परिणाम प्रिंट करें।

C++ कार्यान्वयन

#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