C++で各変数が1つ欠けたn個の和の方程式からn個の変数を求める方法

この問題では、(n−1)個の変数の和から構成される配列 sum[] が与えられます。各要素は、対応する1つの変数を除いた残りすべての変数の和を表しています。

Sum[1] = x2 + x3 + x4 + … + xn
Sum[2] = x1 + x3 + x4 + … + xn
.
.
Sum[i] = x1 + … + x(i-1) + x(i+1) + … + xn
.
.
Sum[n] = x1 + x2 + x3 + … + x(n-1)

この記事のゴールは、これらの式から x1, x2, …, xn の値を求めることです。

入力例

sum[] = {6, 6, 6, 6, 6, 6, 6}

出力例

x1 = 1, x2 = 1, x3 = 1, x4 = 1, x5 = 1, x6 = 1, x7 = 1

説明

arr[1] = 1 + 1 + 1 + 1 + 1 + 1 = 6

解法アプローチ

まず、すべての変数の総和を sumX と定義します。

sumX = x1 + x2 + x3 + … + xn

すると、sum 配列の各要素は次のように書き換えられます。

sum[1] = x2 + x3 + x4 + … + xn
       = -x1 + (x1 + x2 + x3 + … + xn)
       = sumX - x1

同様に、以下の関係が成り立ちます。

sum[2] = sumX - x2
sum[3] = sumX - x3
.
sum[i] = sumX - xi
.
sum[n] = sumX - xn

次に、sum 配列の全要素を合計してみましょう。

Sum[1] + Sum[2] + … + Sum[n] = (sumX - x1) + (sumX - x2) + … + (sumX - xn)
arrSum = n × sumX - (x1 + x2 + x3 + … + xn)
arrSum = n × sumX - sumX
arrSum = sumX × (n - 1)

したがって、総和 sumX は次の式で求められます。

sumX = arrSum / (n - 1)

この sumX の値が分かれば、各変数は「総和から対応する sum の値を引く」だけで簡単に計算できます。

x1 = sumX - sum[1]
x2 = sumX - sum[2]
..
xi = sumX - sum[i]
..
xn = sumX - sum[n]

計算量

配列の走査は2回だけで済むため、時間計算量は O(n)、追加メモリも不要で空間計算量は O(1) と非常に効率的です。

C++実装例

上記の解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;
void calcSumVariables(int sum[], int n) {
    float SUMX = 0;
    for (int i = 0; i < n; i++) {
        SUMX += sum[i];
    }
    SUMX /= (n - 1);
    for (int i = 0; i < n; i++)
        cout << "\nx" << (i + 1) << " = " << (SUMX - sum[i]);
}
int main(){
    int sum[] = {3, 8, 6, 7, 4, 5, 9 };
    int N = sizeof(sum) / sizeof(sum[0]);
    cout << "The value of variables that form the sum are ";
    calcSumVariables(sum, N);
    return 0;
}

出力

x1 = 4
x2 = -1
x3 = 1
x4 = 0
x5 = 3
x6 = 2
x7 = -2

このように、総和 sumX を一度求めてしまえば、あとは引き算だけで n 個の変数すべてを復元できることが分かります。連立方程式を直接解く必要がないため、実装もシンプルになります。