C++ में दिए गए ऐरे में लगातार तत्वों के GCD से ऐरे बनाएं

मान लें हमारे पास n तत्वों का एक ऐरे A[] है। हमें एक और ऐरे B[] ढूंढना है, जिसका आकार n+1 हो, जैसे कि B[i] और B[i+1] का GCD A[i] हो। यदि कई समाधान हैं, तो उनमें से एक प्रिंट करें जिसका ऐरे योग न्यूनतम हो। इसलिए यदि A = [1, 2, 3], तो आउटपुट [1, 2, 6, 3] होगा।

जब A में केवल एक तत्व हो मान लें K, तो B = [K, K]। तो B[0] A[0] होगा। अब मान लें हम इंडेक्स i तक हो चुके हैं, तो हमने पहले ही इंडेक्स i प्रोसेस कर लिया है, और B[i+1] की गणना कर ली है। अब B[i+1] और B[i+2] का GCD = A[i+1], फिर B[i+2] और B[i+3] का GCD = A[i+2]। तो B[i+2] >= A[i+1], A[i+2] का LCM। चूंकि हम न्यूनतम योग चाहते हैं, तो हम B[i+2] का न्यूनतम मान चाहते हैं, इसलिए B[i+2] = A[i+2] और A[i+3] का LCM।

उदाहरण

#include <iostream>
#include <algorithm>
using namespace std;

int getLCM(int a, int b) {
    return (a * b) / __gcd(a, b);
}

void gcdArray(int A[], int n) {
    cout << A[0] << " ";
    for (int i = 0; i < n - 1; i++)
        cout << getLCM(A[i], A[i + 1]) << " ";
    cout << A[n - 1];
}

int main() {
    int A[] = {1, 2, 3};
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Constructed array: ";
    gcdArray(A, n);
}

आउटपुट

Constructed array: 1 2 6 3