JavaScriptで配列の合計を指定の数で割り切れるようにする、削除すべき最小の部分配列の求め方

本記事では、第一引数に正の整数の配列、第二引数に正の整数を受け取るJavaScript関数を実装します。この関数の目的は、元の配列から削除すべき最小の部分配列（連続する要素）の長さを求めて返すことです。削除後の残りの要素の合計が、第二引数で指定された数で割り切れる状態になる必要があります。

問題の例

たとえば、次のような入力が与えられたとします。

const arr = [3, 8, 2, 6];
const num = 9;

配列全体の合計は 3 + 8 + 2 + 6 = 19 であり、これを 9 で割ると余りは 1 になります。ここで部分配列 [8, 2] を削除すると、残りの合計は 3 + 6 = 9 となり、見事に 9 で割り切れます。1つの要素だけを削除してもこの条件は満たせないため、期待される出力は次のとおりです。

const output = 2;

解法のコード

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

const arr = [3, 8, 2, 6];
const num = 9;

const minimumDeletion = (arr = [], num) => {
    // 配列全体の合計をnumで割った余り
    const diff = arr.reduce((a, b) => a + b) % num;
    // 余りが0なら削除不要、それ以外は仮の最大値を設定
    let res = diff == 0 ? 0 : arr.length;
    // 累積和の余りごとの最初の出現位置を記録するマップ
    for (let i = 0, sum = 0, map = {0: -1}; i < arr.length; i++) {
        sum += arr[i];
        // 削除候補となる部分配列の終点に対応する余りを計算
        const target = (sum % num - diff + num) % num;
        if (map[target] != undefined) {
            res = Math.min(res, i - map[target]);
        }
        map[sum % num] = i;
    }
    // 条件を満たす削除が不可能な場合は-1を返す
    return res == arr.length ? -1 : res;
};
console.log(minimumDeletion(arr, num));

アルゴリズムのポイント

• 余りの計算：まず配列全体の合計を num で割った余り（diff）を求めます。diff が 0 であれば、そもそも削除は一切不要なので答えは 0 です。
• 削除すべき部分配列の性質：「合計を num で割った余りが diff と一致する部分配列」を見つけて取り除けば、残りの合計は必ず num の倍数になります。
• 累積和とハッシュマップによる高速化：各時点での累積和の余りと、その余りが最初に出現したインデックスをマップに記録します。これにより、二重ループを使わずに O(n) の時間計算量で最短の部分配列を効率的に探索できます。
• 不可能なケースへの対応：どの部分配列を削除しても条件を満たせない場合は -1 を返す仕様になっています。

実行結果

上記のコードをコンソールで実行すると、次の出力が得られます。

2