C++の配列パズル：減算演算子を使わずに「自分以外の要素の合計」を求める方法

今回は、配列に関する興味深い問題を紹介します。n個の要素を持つ配列が与えられ、それをもとに同じくn個の要素を持つ別の配列を作成します。ただし、新しい配列のi番目には、元の配列のi番目の要素を除いたすべての要素の合計を格納します。さらに重要な制約として、減算演算子（-）を使用してはいけないという条件が課されています。

問題のポイント

もし減算が使えるのであれば、話は簡単です。まず全要素の合計を求めておき、そこからi番目の要素を引いた値を新しい配列のi番目に格納すればよいだけです。しかし、この問題では減算が禁止されているため、別のアプローチが必要になります。

そこで、各位置i（0〜n-1）について、その位置の要素をスキップしながら、毎回要素を一つずつ加算していく方法を採用します。以下のアルゴリズムで具体的な流れを確認しましょう。

アルゴリズム

sumArray(arr, n)

begin
    define an array called res of size n
    for all elements i in arr, do
        sum := 0
        for all elements j in arr, do
            if i and j are not same, then
                sum := sum + arr[j]
            end if
        done
        res[i] = sum
    done
    return res
end

処理の流れはシンプルです。外側のループで結果を格納する位置iを決め、内側のループで配列全体を走査します。このとき「i と j が異なる場合のみ」加算することで、i番目の要素自身を除外した合計が得られます。

C++での実装例

#include<iostream>
using namespace std;
void printArray(int arr[], int n) {
    for(int i = 0; i<n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
void sumArray(int arr[], int resArr[], int n) {
    for(int i = 0; i<n; i++) {
        int sum = 0;
        for(int j =0; j<n; j++ ) {
            if(i != j) {
                sum += arr[j];
            }
        }
        resArr[i] = sum;
    }
}
main() {
    int myArr[7] = {5, 4, 7, 6, 9, 2, 3};
    int resArr[7];
    cout << "Initial Array: ";
    printArray(myArr, 7);
    sumArray(myArr, resArr, 7);
    cout << "Final Array: ";
    printArray(resArr, 7);
}

出力結果

Initial Array: 5 4 7 6 9 2 3
Final Array: 31 32 29 30 27 34 33

出力の解説

結果を検証してみましょう。元の配列は {5, 4, 7, 6, 9, 2, 3} です。

• 0番目：5を除いた合計 → 4+7+6+9+2+3 = 31
• 1番目：4を除いた合計 → 5+7+6+9+2+3 = 32
• 2番目：7を除いた合計 → 5+4+6+9+2+3 = 29

以降も同様に、自分自身の要素だけを除外した合計が正しく格納されていることがわかります。

計算量について

この手法は二重ループを使用するため、時間計算量は O(n²) となります。一方、結果を格納する配列が必要なだけで追加のメモリはほとんど使わないため、空間計算量は O(n)（補助領域としてはO(1)）です。減算が禁止されている制約下では、この素直な二重ループによる実装が最も分かりやすい解法と言えます。