C++-এ সব সম্ভাব্য সাব-অ্যারে থেকে ন্যূনতম LCM এবং GCD

ধরুন আমাদের একটি অ্যারে arr আছে আকার N। এতে Nটি ধনাত্মক সংখ্যা আছে। আমাদের সব সম্ভাব্য সাব-অ্যারে থেকে ন্যূনতম উপাদান বের করতে হবে। ধরুন অ্যারেটি হল {2, 66, 14, 521}, তবে ন্যূনতম LCM হল ২, এবং GCD হল ১।

আমরা এই সমস্যাটি গ্রিডি পদ্ধতিতে সমাধান করব। যদি উপাদানের সংখ্যা কম করি, তবে LCM কম হবে, আর যদি অ্যারের আকার বাড়াই, তবে GCD কম হবে। আমাদের অ্যারেটি থেকে সবচেয়ে ছোট উপাদানটি খুঁজে বের করতে হবে, যা একক উপাদান, সেটিই প্রয়োজনীয় LCM। GCD-এর জন্য, GCD হবে অ্যারে সব উপাদানের GCD।

C++ প্রোগ্রাম উদাহরণ

#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);
    return 0;
}

আউটপুট

LCM: 2, GCD: 1