JavaScript：配列の全要素の倍数となる最小のn桁の数を見つける方法

JavaScriptでは、第一引数に数値（桁数n）、第二引数に数値の配列を受け取り、その配列内のすべての要素の倍数となる最小のn桁の数を返す関数を作成する方法を考えてみましょう。

もし条件を満たすn桁の数が存在しない場合は、すべての要素の倍数となる最小の数（最小公倍数）を返します。

問題の概要

例として、次のような配列が与えられたとします。

const arr = [12, 4, 5, 10, 9]

この場合、n = 2 の場合も n = 3 の場合も、出力は 180 となります。

これは、180 が配列の全要素（12, 4, 5, 10, 9）で割り切れる最小の数だからです。2桁の範囲には条件を満たす数が存在しないため、探索は3桁以降へと続けられ、結果的に 180 に到達します。

実装例

以下が実際のコードです。

const arr = [12, 4, 5, 10, 9]
const num1 = 2;
const num2 = 3;
const allDivides = (arr, num) => arr.every(el => num % el === 0);
const smallestMultiple = (arr, num) => {
    let smallestN = Math.pow(10, (num - 1));
    while(!allDivides(arr, smallestN)){
        smallestN++;
    };
    return smallestN;
};
console.log(smallestMultiple(arr, num1));
console.log(smallestMultiple(arr, num2));

実行結果

このコードを実行すると、コンソールには次のように出力されます。

180
180

コードの解説

allDivides 関数

Array.prototype.every() メソッドを使い、配列のすべての要素が対象の数を割り切れるかどうかを判定します。すべての要素に対して num % el === 0 が成立する場合にのみ true を返します。

smallestMultiple 関数

まず Math.pow(10, num - 1) によって最小のn桁の数を求めます。例えば n = 2 なら 10 からスタートし、条件を満たさない間は候補の数を1ずつ増やしながら繰り返しチェックを行います。全要素の倍数となる数が見つかった時点で、その値を返します。

最小公倍数（LCM）による効率化

上記の方法は線形探索のため、n が大きい場合や配列要素の最小公倍数が大きい場合には処理に時間がかかる可能性があります。そこで、最小公倍数をあらかじめ計算しておけば、答えを直接かつ高速に導き出せます。

const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
const lcmOfArray = (arr) => arr.reduce((acc, el) => acc * el / gcd(acc, el));
const smallestMultipleFast = (arr, num) => {
  const l = lcmOfArray(arr);
  const min = Math.pow(10, num - 1);
  return Math.ceil(min / l) * l;
};
console.log(smallestMultipleFast(arr, num1)); // 180
console.log(smallestMultipleFast(arr, num2)); // 180

ユークリッドの互除法で最大公約数（GCD）を求め、reduce() と組み合わせることで配列全体の最小公倍数を算出できます。あとは「n桁の最小値以上となる最小の公倍数」を計算すれば、同じ答えを瞬時に得ることができます。