Bài toán: Between Two Sets
Source: https://www.hackerrank.com/challenges/between-two-sets/problem
Mức độ : Easy
Tóm tắt bài toán : Cho 2 mảng số nguyên với điều kiện cho trước. Tìm dãy các số giữa hai mảng sao cho nó là số chia hết cho tất cả phần tử của mảng thứ nhất và các phần tử mảng thứ 2 chia hết cho số đó.
Solution:
Idea: Từ bài toán => Các số cần tìm phải là bội số chung của mảng thứ nhất và ước số chung của mảng thứ hai.
Xét điều kiện thứ nhất: Các số nằm giữa là bội số chung của mảng thứ nhất => Ta cần phải tìm bội số chung nhỏ nhất (LCM) là số bắt đầu kiểm tra tiếp. Với khoảng cách các số tiếp theo là bằng LCM.
Xét điều kiện thứ hai: Các số nằm giữa là ước số chung của mảng thứ hai => Ta cần phải tìm ước số chung nhỏ nhất (GCD) là số kết thúc của dãy các số đang xét.
Vậy tìm GCD thế nào ? Có nhiều cách dưới đây là 1 só cách có thể tham khảo: https://nguyenvanhieu.vn/thuat-toan-tim-uoc-chung-lon-nhat/
Ta áp dụng tìm 2 số đầu trong mảng rồi dùng chính ước chung đấy tìm tiếp để đến kết quả cuối cùng.
Tìm LCM thế nào ? Ta có thể dùng cách LCM(a,b)=(a*b)/GCD(a,b);
Cuối cùng ta check xem trong khoảng giữa LCM mảng 1 và GCD mảng 2 có bao nhiêu số mà GCD mảng 2 chia hết thì tăng biến đếm count lên 1 đơn vị.
Time complexity: O(nlog(n))
Code JavaScript tham khảo :

function lcm(x,y){
    return (x*y)/gcd(x,y);
}
function gcd(x,y) {
    while(x!=y) {
        if(x>y)x-=y;
        else y-=x;
    }
    return x;
}
function getTotalX(a, b) {
    for(let i=0;i<a.length;i++){
        if(a[i]>b[0]) return 0;
    }
    let lcmultiple = a[0];
    for(let i=1;i<a.length;++i){
        lcmultiple=lcm(lcmultiple,a[i]);
    }
    let gcdivisor = b[0];
    for(let i=1;i<b.length;++i) {
        gcdivisor=gcd(gcdivisor,b[i]);
    }
    let count =0;
    for(let i=lcmultiple;i<=gcdivisor;i+=lcmultiple) {
        if(gcdivisor%i===0) count++;
    }
    return count;
}

Minh (Conal Dev)