JavaScriptで「nで割り切れる部分配列の合計」を求める方法

問題の概要

JavaScriptで、第一引数として数値の配列 arr を、第二引数として数値 num を受け取る関数を作成する必要があります。この関数は、要素の合計が num で割り切れるような連続した（コンティギュアスな）非空の部分配列の個数を返します。

たとえば、関数への入力が次の場合を考えてみましょう。

const arr = [4, 5, 0, -2, -3, 1];
const num = 5;

この場合、出力は次のようになります。

const output = 7;

出力の解説

合計が5で割り切れる部分配列は、以下の7つ存在します。

[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

アプローチ：累積和と剰余（モジュロ）の活用

この問題を効率的に解く鍵となるのは、累積和（プレフィックスサム）と剰余の性質です。

基本的な考え方

2つの位置における累積和の剰余が同じである場合、その間の部分配列の合計は必ず num で割り切れます。したがって、以下の手順で答えを求められます。

1. 配列を走査しながら累積和を計算し、それを num で割った余りごとに出現回数を記録する。
2. 同じ余りが出現した回数から、組み合わせの数 n × (n − 1) / 2 を計算する。これは、その余りを持つ2つの累積和のペアの総数に等しい。
3. 余りが0になる累積和は、それ自体が先頭からの部分配列として割り切れる合計を持つため、その個数も結果に加算する。

なお、JavaScriptでは負の数に対する % 演算子が負の結果を返すことがあるため、((sum % num) + num) % num のように書くことで、常に0以上の正しい余りを取得できます。

コード例

実際のコードは以下のようになります。

const arr = [4, 5, 0, -2, -3, 1];
const num = 5;

const divisibleSum = (arr = [], num = 1) => {
    const map = {};
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
        sum += arr[i];
        // 負の数にも対応した安全な剰余計算
        const key = ((sum % num) + num) % num;
        map[key] = map[key] + 1 || 1;
    }
    let s = 0;
    // 同じ余りを持つペアの組み合わせを集計
    for (let i = 0; i < num; i++) {
        if (map[i] > 1) {
            s += (map[i] * (map[i] - 1)) / 2;
        }
    }
    // 余り0の累積和は単体でも条件を満たす
    return s + (map[0] || 0);
};
console.log(divisibleSum(arr, num));

実行結果

コンソールには次の出力が表示されます。

7

計算量について

このアプローチの時間計算量は O(n)、空間計算量は O(num) です。すべての部分配列を総当たりでチェックする素朴な方法（時間計算量 O(n²)）と比べて大幅に効率的であり、大きな入力に対しても高速に動作します。