Tìm ước chung lớn nhất của mảng số trong JavaScript

Mô tả bài toán

Viết hàm tìm số lớn nhất chia hết cho tất cả các phần tử trong mảng (ước chung lớn nhất - GCD của mảng).

Ví dụ minh họa

const arr = [4, 6, 34, 76, 78, 44, 34, 26, 88, 76, 42];

const dividesAll = el => {
  const result = [];
  for (let num = Math.floor(el / 2); num > 1; num--) {
    if (el % num === 0) result.push(num);
  }
  return result;
};

const dividesArray = arr => {
  return arr.map(dividesAll).reduce((acc, val) => 
    acc.filter(el => val.includes(el)));
};

console.log(dividesArray(arr));

Kết quả

[ 2 ]

Phân tích

Code gốc tìm tất cả ước của mỗi số, sau đó giao nhau. Cách này O(n * max(arr)) - rất chậm với số lớn.

Thuật toán Euclid tối ưu O(n log max)

const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
const gcdArray = arr => arr.reduce((a, b) => gcd(a, b));

Kết quả

2