C++で配列を均等に分割するために挿入すべき最小の正の整数を求める方法

問題概要

N個の正の整数からなる配列が与えられます。この配列内の任意の2つの要素の間に、ある正の整数を挿入したとき、左側の部分配列の合計と右側の部分配列の合計が等しくなるようにしたいと考えます。新しく挿入した整数は、左右どちらか一方の部分配列に含まれるものとします。本記事では、この条件を満たすために挿入すべき正の整数のうち、最小の値を求める方法を解説します。

具体例

たとえば、配列が {3, 2, 1, 5, 7, 10} の場合、答えは 6 になります。値 6 を 5 と 7 の間に挿入すると、左右の部分配列の合計は次のように一致します。

3 + 2 + 1 + 5 + 6 = 17
7 + 10 = 17

アルゴリズムの考え方

• まず、配列全体の合計を S とします。
• インデックス i まで(その要素自身を含む)の左側の合計を求めます。これを L とします。
• このとき、インデックス i+1 以降の部分配列の合計は S − L で表せます。これを R とします。
• 左右の合計が等しくなるようにするには、L と R のうち大きい方を小さい方の値に揃える必要があります。つまり、「大きい方の合計 − 小さい方の合計」が、挿入すべき正の整数の値になります。
• すべての分割位置についてこの差を計算し、その最小値を答えとします。

C++での実装例

#include <iostream>
#include <numeric>
#include <climits>
using namespace std;

// 挿入すべき最小の正の整数を求める関数
int getMinimumSplitPoint(int *arr, int n) {
    int sum = 0;
    sum = accumulate(arr, arr + n, sum); // 配列全体の合計 S
    int leftSum = 0;
    int rightSum = 0;
    int minValue = INT_MAX;
    for (int i = 0; i < n - 1; ++i) {
        leftSum += arr[i];        // インデックス i までの左側の合計 L
        rightSum = sum - leftSum; // 右側の合計 R
        if (leftSum > rightSum) {
            int e = leftSum - rightSum;
            if (e < minValue) {
                minValue = e;
            }
        } else {
            int e = rightSum - leftSum;
            if (e < minValue) {
                minValue = e;
            }
        }
    }
    return minValue;
}

int main() {
    int arr[] = {3, 2, 1, 5, 7, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int minValue = getMinimumSplitPoint(arr, n);
    cout << "Element " << minValue << " needs to be inserted\n";
    return 0;
}

出力結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

Element 6 needs to be inserted

計算量

このアルゴリズムは配列を一度だけ走査すればよいため、時間計算量は O(N) です。また、配列全体の合計と現在の左側の合計を保持するだけで処理できるため、追加で必要なメモリ領域は O(1) に抑えられます。ループを最後の要素の1つ手前(n − 1)までにしているのは、挿入位置が必ず「2つの要素の間」でなければならないためです。非常にシンプルかつ効率的な解法といえます。