หา LCM และ GCD น้อยที่สุดที่เป็นไปได้ในทุก sub-array ใน C++

บทนำ

กำหนดอาร์เรย์ arr ขนาด N ประกอบด้วยจำนวนบวก ต้องการหาค่า LCM และ GCD น้อยที่สุดจากทุก sub-array ที่เป็นไปได้

ตัวอย่าง: อาร์เรย์ {2, 66, 14, 521} → LCM น้อยที่สุด = 2, GCD น้อยที่สุด = 1

แนวคิดแบบ Greedy

• ถ้าลดจำนวนสมาชิก LCM จะน้อยลง → LCM น้อยที่สุดคือสมาชิกที่มีค่าน้อยที่สุดในอาร์เรย์ (sub-array ขนาด 1)
• ถ้าเพิ่มขนาดอาร์เรย์ 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