C++で配列をバランスさせるために追加する最小の値を見つける方法

配列のバランスを取る値とは

n個の要素（nは偶数）を持つ配列Aがあるとします。この配列をバランスさせるために必要な値を見つけるのが課題です。配列のサイズが偶数であるため、配列を前半と後半の2つに分割できます。バランスが取れている状態とは、前半の要素の合計と後半の要素の合計が一致することを指します。

例えば、配列が A = [1, 2, 3, 2, 5, 3] の場合を考えてみましょう。前半 [1, 2, 3] の合計は6、後半 [2, 5, 3] の合計は10です。この2つの合計の差は4なので、配列をバランスさせるためには4という値が必要になります。

アルゴリズムの考え方

この問題の解法は非常にシンプルです。以下の手順で求めることができます。

1. 配列の前半（インデックス0から n/2 - 1 まで）の要素の合計を計算する
2. 配列の後半（インデックス n/2 から n - 1 まで）の要素の合計を計算する
3. 両者の合計の絶対差を計算して返す

この絶対差こそが、配列をバランスさせるために追加すべき最小の値となります。

C++による実装例

#include<iostream>
#include<cmath>
using namespace std;

int getValueToBalance(int a[], int n) {
    int left_sum = 0;
    for (int i = 0; i < n/2; i++)
        left_sum += a[i];
    int right_sum = 0;
    for (int i = n/2; i < n; i++)
        right_sum += a[i];
    return abs(left_sum - right_sum);
}

int main() {
    int arr[] = {1, 2, 3, 2, 5, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "The number for balancing: " << getValueToBalance(arr, n);
}

実行結果

The number for balancing: 4

コードの解説

関数 getValueToBalance では、まず前半の要素を順番に加算して left_sum を求め、続いて後半の要素を加算して right_sum を求めています。最後に abs() 関数を使って2つの合計の差の絶対値を返すことで、どちらの半分が大きい場合でも正しくバランス値を取得できます。

このアルゴリズムの計算量は、配列を一度だけ走査するため O(n) となり、非常に効率的です。補助的な記憶領域も定数 O(1) で済むため、メモリの面でも優れた解法といえます。