JavaScriptで配列から1要素を削除して奇数・偶数インデックスの合計を等しくする方法の数を求める

数値の配列を唯一の引数として受け取るJavaScript関数を作成することを目標としましょう。

この関数は、配列から1つの要素を削除したときに、奇数インデックスの要素の合計と偶数インデックスの要素の合計が等しくなるような削除方法を探します。さらに、条件を満たすすべてのユニークな削除方法の個数をカウントして返す必要があります。

具体例で理解する

入力配列が次の場合を考えてみます。

const arr = [2, 6, 4, 2];

このときの出力は 2 になります。これは、インデックス1の「6」とインデックス3の「2」の、2つの要素がそれぞれ削除対象として条件を満たすためです。

6 を削除した場合：

[2, 4, 2] → 奇数インデックスの合計 = 偶数インデックスの合計 = 4

末尾の 2 を削除した場合：

[2, 6, 4] → 奇数インデックスの合計 = 偶数インデックスの合計 = 6

実装コード

以下がその実装例です。

const arr = [2, 6, 4, 2];
const possibleWays = (arr = []) => {
    const sum = new Array(arr.length);
    let res = 0;
    let oddSum = 0;
    let evenSum = 0;
    for (let i = 0; i < arr.length; ++i) {
        if (i % 2 === 0) sum[i] = (evenSum += arr[i]);
        else sum[i] = (oddSum += arr[i]);
    }
    for (let i = 0; i < arr.length; ++i) {
        if (i % 2 === 0) {
            if (2 * sum[i] - arr[i] + oddSum === 2 * (sum[i - 1] || 0) + evenSum) ++res;
        } else if (2 * sum[i] - arr[i] + evenSum === 2 * (sum[i - 1] || 0) + oddSum) {
            ++res;
        }
    }
    return res;
};
console.log(possibleWays(arr));

出力結果

コンソールには次のように表示されます。

2

アルゴリズムのポイント

• 時間計算量 O(n)： 各要素を実際に削除して毎回合計を再計算する素朴なアプローチでは O(n²) の計算量が必要ですが、累積和（プレフィックスサム）を活用することで線形時間で解くことができます。
• 最初のループ： インデックスを順に走査しながら、偶数インデックスと奇数インデックスそれぞれの累積和を配列 sum に記録していきます。
• 2番目のループ： 要素を実際に取り除いて配列を組み立て直すことなく、累積和をもとに「削除後の偶数インデックス合計」と「削除後の奇数インデックス合計」を数式で直接算出し、両者が一致するかを判定しています。