ধরি একটি অ্যারে A[] আছে n উপাদান সহ। আমাদের একটি অন্য অ্যারে 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
