【C++】配列内の「残りの要素の合計と等しい要素」を見つける方法

この記事では、n個の正の整数からなる配列 arr[] が与えられたとき、その中から「残りのすべての要素の合計と等しい要素」を見つけるアルゴリズムを解説します。

問題の概要：配列内の要素のうち、その要素自身を除いた他のすべての要素の合計と値が一致するものを見つける必要があります。

例で問題を理解しよう

入力：arr[] = { 5, 4, 17, 1, 7 }

出力：17

説明：

残りの要素の合計は (5 + 4 + 1 + 7) = 17 となり、これは要素 17 と一致します。したがって答えは 17 です。

解法のアプローチ

この問題には、非常にシンプルで効率的な解法があります。それは「配列の全要素の合計は、該当する要素の値の2倍になる」という性質を利用する方法です。なぜなら、対象の要素を除いた合計がその要素自身と等しいということは、全体の合計がその要素の2倍になるためです。

具体的には、以下の手順で解きます。

ステップ1：配列の全要素の合計を求める。
ステップ2：配列の各要素についてループ処理を行う。

ステップ2.1：「arr[i] × 2 == 配列の合計」であるかを判定する。

ステップ2.1.1：条件が真であれば、フラグを立ててループを抜ける。

ステップ2.2.1：条件が偽であれば、そのまま次の要素へ進む。

ステップ3：フラグが立っていれば、該当する要素 arr[i] を出力する。
ステップ4：それ以外の場合は「該当する要素は見つかりませんでした」と出力する。

解法の動作を示すサンプルプログラム

コード例

#include <iostream>
using namespace std;

void findElemenetInArray(int arr[], int n) {
    
    int arraySum = 0;
    int flag = 0, i;
    for (i = 0; i < n; i++)
        arraySum += arr[i];

    for (i = 0; i < n; i++)
        if ( (2*arr[i]) == arraySum ) {
            flag = 1;
            break;
        }
            
    if(flag)
        cout<<arr[i];
    else
        cout<<"No such element is found!";
    
}

int main() {
    int n = 5;
    int arr[n] = { 5, 4, 7, 1, 17 };
    findElemenetInArray(arr, n);
    return 0;
}

出力結果

17

計算量について

このアルゴリズムの計算量を整理しておきましょう。

• 時間計算量：O(n) ― 配列を2回走査するだけなので、要素数に対して線形の時間で処理が完了します。
• 空間計算量：O(1) ― 合計値とフラグを格納する変数のみを使用するため、追加のメモリは不要です。

このように、配列の総和を先に計算しておくことで、各要素について毎回「残りの要素の合計」を求め直す必要がなくなり、効率的に解を導き出せるのがポイントです。