C++で与えられた数が最初のn個の自然数の和かどうかを判定する方法

この問題では、ある数値 num が与えられ、それが最初の n 個の自然数の和になっているかどうかを判定します。

問題の説明

与えられた数が、1から始まる連続する自然数（1+2+3+…+n）の総和として表せるかどうかを確認し、表せる場合はその n の値を求めます。

入出力例で問題を理解しよう

入力：num = 55

出力：yes, 10

説明：

55 は最初の 10 個の自然数の和、つまり 1+2+3+4+5+6+7+8+9+10 に一致します。

解法アプローチ①：累積和によるシンプルな方法

最も単純なアプローチは、n を 1 から順に増やしながら自然数の和を計算し、その値が num と等しくなるか、num を超えるまで繰り返す方法です。

• 和がちょうど num に一致した場合 → その時点の n を返す
• 和が num を超えた場合 → -1 を返す（該当なし）

この解法の実装プログラム

サンプルコード

#include <iostream>
using namespace std;

int isNatSum(int num){

    int sum = 0;
    for (int n = 1; sum < num; n++) {
        sum += n;
        if (sum == num)
            return n;
    }
    return -1;
}

int main(){

    int num = 55;
    int n = isNatSum(num);
    if(n == -1)
        cout<<"The value is not sum of natural numbers";
    else
        cout<<"The value is a sum of first "<<n<<" natural numbers";
    return 0;
}

出力

The value is a sum of first 10 natural numbers

この方法でも正しく動作しますが、計算量は O(n) となるため、より効率的な解法が望まれます。

解法アプローチ②：数学の公式を使った効率的な方法

最初の n 個の自然数の和は、次の公式で表されます。

sum = n × (n + 1) / 2

今回は「和」が分かっていて「n」を求めたいので、これを二次方程式に変形します。

=> 2 × Sum = n² + n

=> n² + n − 2 × Sum = 0　（二次方程式）

この二次方程式を解くと、n は次の式で求められます。

n = (−1 + √(1 + 8 × Sum)) / 2

求めた n が整数（小数部分を持たない値）であれば、num は自然数の和であると判定できます。この方法なら O(1) の定数時間で答えを得られます。

この解法の実装プログラム

サンプルコード

#include <iostream>
#include <math.h>
using namespace std;

int isNatSum(int num){

    int n = ( -1+ sqrt (1 + (8*num) ))/2;
    if(ceil(n)==floor(n)){
        return n;
    }
    return -1;
}

int main(){

    int num = 55;
    int n = isNatSum(num);
    if(n == -1)
        cout<<"The value is not sum of natural numbers";
    else
        cout<<"The value is a sum of first "<<n<<" natural numbers";
    return 0;
}

出力

The value is a sum of first 10 natural numbers

まとめ

与えられた数が最初の n 個の自然数の和かどうかを判定するには、累積和を順に計算する方法（O(n)）と、二次方程式の解の公式を利用する方法（O(1)）があります。大きな数値を扱う場合は、公式を使った方法が圧倒的に効率的です。