Ước chung lớn nhất và bội số chung nhỏ nhất của mảng số nguyên

Chào mừng các bạn đã quay trở lại với thachleblog. Để “đổi gió” cho blog, thỉnh thoảng mình sẽ có những bài code challenge về các giải thuật đơn giản. Để bắt đầu cho phần giải thuật này, bài viết hôm nay mình sẽ trình bày giải thuật tìm ước chung lớn nhất và bội số chung nhỏ nhất cho mảng các số nguyên.

Yêu cầu

Tìm ước số chung lớn nhất và bội số chung nhỏ nhất của mảng các số nguyên.

– Ước chung lớn nhất: gcd (greatest common divisor) là số nguyên x lớn nhất sao cho các phần tử của mảng đều chia hết cho x

– Bội số chung nhỏ nhất: lcm (least common multiple) là số nguyên x nhỏ nhất sao cho x chia hết cho tất cả các phần tử của mảng

Input

a[] = {12, 8, 16}

Output

gcd(a): 4

lcm(a): 48

Giải thuật

– Tìm gcd

+ Đầu tiên mình sẽ tìm a[i] là phần tử nhỏ nhất mảng

+ Tiếp theo thực hiện kiểm tra các phần tử trong mảng có chia hết cho a[i] hay không, nếu chia hết thì a[i] là phần tử cần tìm

+ Nếu không, mình sẽ cho a[i] giảm dần về 1, nếu có giá trị nào mà tất cả phần tử trong mảng đều chia hết thì đó là giá trị cần tìm

– Tìm lcm

+ Đầu tiên mình sẽ tìm a[i] là phần tử lớn nhất nhất mảng

+ Tiếp theo thực hiện kiểm tra a[i] có chia hết cho các phần tử trong mảng không, nếu chia hết thì a[i] là phần tử cần tìm

+ Nếu không, mình sẽ cho a[i] tăng dần đến cấp số cộng, nếu có giá trị nào mà tất cả phần tử trong mảng đều chia hết thì đó là giá trị cần tìm

Code minh họa

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
 
public class Solution {
 
    static int max(int[] a) {
        int max = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        return max;
    }
 
    static int min(int[] a) {
        int min = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] < min) {
                min = a[i];
            }
        }
        return min;
    }
 
    static int lcm(int[] a) {
        int max = max(a);
        int result = max(a);
        int k = 1;
        boolean flag = true;
        int length = a.length;
        do {
            for (int i = 0; i < a.length; i++) {
                if (result % a[i] != 0) {
                    k++;
                    result = max * k;
                } else if (i == length - 1) {
                    flag = false;
                    break;
                }
            }
        } while (flag);
 
        return result;
    }
 
    static int gcd(int[] a) {
        int result = min(a);
        int length = a.length;
        boolean flag = true;
        do {
            for (int i = 0; i < length; i++) {
                if (a[i] % result != 0) {
                    result--;
                } else if (i == length - 1) {
                    flag = false;
                    break;
                }
            }
        } while (flag);
        return result;
    }

 

Kết

Giải thuật tìm ước chung lớn nhất và bội số chung nhỏ nhất của mảng các số nguyên là 1 phần của bài Between Two Sets trên hackerrank, nếu có hứng thú, các bạn có thể làm tiếp tục để hoàn thành. Sẽ có các test case để đánh giá giải thuật của bạn. Hiện tại thì mình đang luyện để tăng khả năng phản xạ cho giải thuật, hehe.

Đó là phần trình bày của mình về cách ước số chung lớn nhất và bội số chung nhỏ nhất của mảng các số nguyên. Các bạn có giải thuật nào hay hơn, độ phức tạp nhỏ hơn hay có góp ý cho bài của mình thì chia sẻ để chúng ta cùng trao đổi nhé.

Hẹn gặp lại các bạn ở các bài sau. Thanks.

Tham gia bình luận