หาค่าต่ำสุดร่วม (LCM) ของอาร์เรย์ตัวเลขใน Java

บทนำ

LCM (Least Common Multiple) หรือ ค่าต่ำสุดร่วม คือ จำนวนเต็มบวกที่น้อยที่สุดที่หารด้วยทุกตัวเลขในชุดได้ลงตัว

ตัวอย่าง

• LCM ของ 3 และ 4: จำนวนคูณของ 3 = 3,6,9,12,15... จำนวนคูณของ 4 = 4,8,12,16... → LCM = 12
• LCM ของอาร์เรย์ {25, 50, 125, 625} = 625

โปรแกรม Java

public class LCMofArrayOfNumbers {
    public static void main(String args[]) {
        int[] myArray = {25, 50, 125, 625};
        
        // หา LCM ของอาร์เรย์
        int lcm = findLCM(myArray);
        
        System.out.println("LCM of the given array of numbers: " + lcm);
    }
    
    // หา GCD (มากที่สุดร่วม) ด้วย Euclidean Algorithm
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    // หา LCM ของ 2 ตัว: LCM(a,b) = |a*b| / GCD(a,b)
    public static int lcm(int a, int b) {
        return Math.abs(a * b) / gcd(a, b);
    }
    
    // หา LCM ของอาร์เรย์
    public static int findLCM(int[] arr) {
        int result = arr[0];
        for (int i = 1; i < arr.length; i++) {
            result = lcm(result, arr[i]);
        }
        return result;
    }
}

ผลลัพธ์

LCM of the given array of numbers: 625

คำอธิบายอัลกอริทึม

1. GCD (Greatest Common Divisor) - ใช้ Euclidean Algorithm หาตัวหารร่วมมาก
2. LCM ของ 2 ตัว - สูตร: LCM(a,b) = |a × b| / GCD(a,b)
3. LCM ของอาร์เรย์ - คำนวณสะสม: LCM(arr[0], arr[1]) → ผลลัพธ์กับ arr[2] → ...

โค้ดต้นฉบับมีปัญหา

โค้ดต้นฉบับมีลูปซ้อนผิด logic ให้ผลลัพธ์ 250 (ผิด) วิธีข้างต้นให้ผลลัพธ์ถูกต้องคือ 625

Java 8+ Stream API

import java.util.Arrays;

int lcm = Arrays.stream(new int[]{25, 50, 125, 625})
    .reduce(1, (a, b) -> Math.abs(a * b) / gcd(a, b));

Complexity

• Time: O(n log max(arr)) - n = ขนาดอาร์เรย์
• Space: O(1)