【JavaScript】変換操作を繰り返した後に最小となる合計値を求めるアルゴリズム

問題

正の整数からなる配列を受け取るJavaScript関数を作成します。配列の各要素には、次の操作を必要な回数だけ繰り返し適用できます。

if (arr[i] > arr[j]) then arr[i] = arr[i] - arr[j]

これは「より大きい要素から、別の小さい要素の値を引く」という操作です。これ以上どの要素にも操作を適用できなくなった状態(すべての要素が等しくなった状態)になったとき、関数はその配列の合計値を返す必要があります。

解法のアプローチ

この問題の鍵となるのは、引き算を繰り返すと最終的にすべての要素が配列全体の最大公約数(GCD)と等しくなるという数学的な性質です。ユークリッドの互除法と同じ原理で、大きい数から小さい数を引き続けると差は必ずGCDの倍数へと収束していきます。

例えば [6, 9, 21] の場合、GCDは 3 なので、最終的な配列は [3, 3, 3] となり、答えは 9 になります。

コード例

以下が実装コードです。

const arr = [6, 9, 21];
const smallestSum = (arr = []) => {
    const equalNums = arr => arr.reduce((a, b) => {
        return (a === b) ? a : NaN;
    });
    if(equalNums(arr)){
        return arr.reduce((a, b) => {
            return a + b;
        });
    }else{
        const sorted = arr.sort((a, b) => {
            return a - b;
        });
        const last = sorted[arr.length - 1] - sorted[0]
        sorted.pop();
        sorted.push(last);
        return smallestSum(sorted);
    };
};
console.log(smallestSum(arr));

コードの解説

• equalNums: reduce() を使い、隣り合う要素がすべて一致するかどうかを判定するヘルパー関数です。1つでも異なる要素があれば NaN(falsyな値)を返します。
• 終了条件: 全要素が等しい場合は、そこが変換の完了状態なので、reduce() で合計値を計算して返します。
• 再帰ステップ: 等しくない場合は配列を昇順にソートし、最大値から最小値を引いた結果で最大値を置き換えて、自分自身を再帰呼び出しします。

各ステップで配列の総和は必ず減少するため、この再帰処理は有限回で必ず終了します。

出力

コンソールには以下のように出力されます。

9

結果の 9 は、「GCD × 要素数」すなわち 3 × 3 と一致しており、理論どおりの答えになっていることが確認できます。