ধরুন আমাদের কাছে N আকারের একটি অ্যারের অ্যারে আছে। এতে N পজিটিভ সংখ্যা রয়েছে। আমাদের সম্ভাব্য সকল সাবয়ারের ন্যূনতম উপাদান খুঁজে বের করতে হবে। ধরুন অ্যারে হল {2, 66, 14, 521}, তাহলে ন্যূনতম LCM হল 2, এবং GCD হল 1৷
আমরা একটি লোভী পদ্ধতি ব্যবহার করে এই সমস্যার সমাধান করব। যদি আমরা উপাদানের সংখ্যা হ্রাস করি, তাহলে LCM কম হবে, এবং যদি আমরা অ্যারের আকার বাড়াই, GCD কম হবে। আমাদের অ্যারে থেকে ক্ষুদ্রতম উপাদান খুঁজে বের করতে হবে, যা একটি একক উপাদান, যার জন্য LCM প্রয়োজন হবে। GCD-এর জন্য, GCD হবে অ্যারের সমস্ত উপাদানের GCD।
উদাহরণ
#include <iostream>
#include <algorithm>
using namespace std;
int minimum_gcd(int arr[], int n) {
int GCD = 0;
for (int i = 0; i < n; i++)
GCD = __gcd(GCD, arr[i]);
return GCD;
}
int minimum_lcm(int arr[], int n) {
int LCM = arr[0];
for (int i = 1; i < n; i++)
LCM = min(LCM, arr[i]);
return LCM;
}
int main() {
int arr[] = { 2, 66, 14, 521 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "LCM: " << minimum_lcm(arr, n) << ", GCD: " << minimum_gcd(arr, n);
} আউটপুট
LCM: 2, GCD: 1
