C/C++で解く：配列の要素を置き換えて合計値Sと一致させる値Kの求め方

問題の概要

ここでは、配列に関する興味深い問題を扱います。n 個の要素からなる配列と、目標となる合計値 S が与えられます。このとき、次の条件を満たす値 K を配列の中から見つける必要があります。

「配列内の K より大きい要素をすべて K に置き換えたとき、最終的な配列の全要素の合計がちょうど S と等しくなる」。もし条件を満たす K が存在しない場合は、-1 を返します。

例として、配列 {12, 6, 3, 7, 8} と合計値 15 が与えられたケースを考えてみましょう。このときの出力は 3 になります。なぜなら、3 より大きい要素をすべて 3 に置き換えると、配列は {3, 3, 3, 3, 3} となり、その合計はちょうど S = 15 となるからです。

アルゴリズム

getVal(arr, n, S) の処理手順は以下の通りです。

開始
    配列 arr を昇順にソートする
    sum := 0
    i を 0 から n-1 まで繰り返す:
        もし sum + (arr[i] * (n - i)) が S と等しいならば
            return arr[i]
        終了
        sum := sum + arr[i]
    ループ終了
    return -1
終了

アルゴリズムの考え方

このアルゴリズムのポイントは、配列をあらかじめ昇順にソートしておくことです。ソート後の配列を先頭から走査するとき、インデックス i より前の要素（arr[0] 〜 arr[i-1]）は確定済みとして変数 sum に加算されています。また、残りの n - i 個の要素はすべて arr[i] 以上の値を持っているため、「arr[i] 以降をすべて arr[i] に置き換えた場合の合計」は「sum + arr[i] × (n - i)」という式で一括計算できます。この値が目標の S と一致すれば、その位置の要素 arr[i] こそが求める K です。

計算量はソート部分が支配的となり、時間計算量は O(n log n)、追加のメモリは O(1) で済むため、非常に効率的な手法といえます。

C++での実装例

#include <iostream>
#include <algorithm>
using namespace std;
int getVal(int arr[], int n, int S) {
    sort(arr, arr + n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (sum + (arr[i] * (n - i)) == S) // 条件を満たす場合は現在の値を返す
            return arr[i];
        sum += arr[i];
    }
    return -1;
}
int main() {
    int S = 15;
    int arr[] = { 12, 3, 6, 7, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getVal(arr, n, S);
}

実行結果

3

まとめ

本記事では、配列を昇順にソートしながら累積和を利用することで、条件を満たす値 K を効率的に求める方法を紹介しました。ソートにより「それ以降の要素をまとめて置き換えた場合の合計」を O(1) で判定できるのが最大のポイントです。同様のパターンは、二分探索や累積和を使う他の配列問題にも応用できるので、ぜひ理解しておきましょう。