C++で配列の隠し数（ヒドゥンナンバー）を求めるプログラムの作成方法

この問題では、n個の整数値で構成される配列 arr[] が与えられます。求めるのは、C++で配列の隠し数（ヒドゥンナンバー）を見つけるプログラムです。

問題の説明

隠し数とは、配列の各要素からその数を引いたとき、差の合計がちょうど0になるような数のことを指します。

具体例で問題を確認しましょう。

入力

arr[] = {4, 1, 6, 7, 2}

出力

4

説明： 配列のすべての要素から4を引き、その値を合計すると以下のようになります。

= (1 - 4) + (6 - 4) + (7 - 4) + (2 - 4)
= -3 + 2 + 3 - 2 = 0

このように合計が0になるため、4がこの配列の隠し数であることがわかります。

解法のアプローチ

この問題を解くための手順は次のとおりです。

1. 配列の全要素の合計値を計算する。
2. 合計値を配列の要素数で割る。
3. 割り算の結果が整数（余りなし）であれば、その値が隠し数となる。
4. 割り切れない場合は、隠し数は存在しない（-1を返すなど）。

数学的に考えると、隠し数を x とすると Σ(arr[i] − x) = 0 が成り立ちます。これを変形すると x = Σarr[i] ÷ n となり、隠し数は配列の平均値に等しいことがわかります。つまり、平均値が整数になるときだけ隠し数が存在するのです。

サンプルプログラム

上記の解法を実装したプログラムがこちらです。

#include <iostream>
using namespace std;

int calcHiddenNumber(int arr[], int n){
    long int sum = 0;
    for(int i = 0; i < n; i++){
        sum = sum + arr[i];
    }
    int hidNum = (sum / n);
    if((hidNum * n) == sum)
        return hidNum;
    else
        return -1;
}

int main() {
    int n = 4;
    int arr[] = { 4, 11, 12, 21 };
    cout<<"配列の隠し数は "<<calcHiddenNumber(arr, n);
    return 0;
}

実行結果

配列の隠し数は 12

コードの解説：

• calcHiddenNumber 関数では、まずforループを使って配列の全要素の合計を計算しています。
• 合計を要素数 n で割り、その商を hidNum として保存します。
• hidNum × n が元の合計と一致すれば割り切れたことになるため、hidNum を返します。
• 一致しない場合は隠し数が存在しないので、-1 を返します。

この例では、4 + 11 + 12 + 21 = 48 となり、48 ÷ 4 = 12 で割り切れるため、12 が隠し数として出力されます。

計算量

時間計算量：O(n)（配列を一度だけ走査するため）
空間計算量：O(1)（追加のメモリは不要）