सी ++ में दिए गए सरणी में लगातार तत्वों के जीसीडी से एक सरणी बनाएं

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

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

उदाहरण

#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