C++で数値が3つの連続する整数の和として表現できるか判定する方法

本記事では、ある数値が「3つの連続する整数の和」として表現できるかどうかを判定する方法を解説します。例えば、27という数値は 8 + 9 + 10 のように、3つの連続する整数の合計として書き表すことができます。

問題を解く2つのアプローチ

この問題には、大きく分けて2つの解き方があります。

1. 単純なアプローチ（ナイーブ法）

最初の方法は最も直感的なものです。i + (i + 1) + (i + 2) を計算し、それが対象の数値と一致するかどうかを順番に確認していきます。ただし、この方法では候補を一つずつ調べる必要があるため、数値が大きい場合には非効率になります。

2. 効率的なアプローチ（3の倍数判定）

より効率的なのは、その数値が3で割り切れるかどうかを確認する方法です。

数学的に考えてみましょう。ある数 x が3つの連続する整数 (y − 1)、y、(y + 1) の和で表せるとすると、次の式が成り立ちます。

x = (y − 1) + y + (y + 1) = 3y

つまり、x は必ず3の倍数となります。したがって、「数値が3で割り切れるか」をチェックするだけで判定できるのです。

C++による実装例

#include <iostream>
using namespace std;
bool hasThreeNums(int n) {
    if(n % 3 == 0){
        return true;
    }
    return false;
}
int main() {
    int num = 27;
    if(hasThreeNums(num)){
        cout << "Can be represented";
    }else{
        cout << "Cannot be presented";
    }
}

出力結果

Can be represented

まとめ

3つの連続する整数の和は、必ず中央の値の3倍になります。そのため、判定条件は非常にシンプルで、剰余演算子 % を用いた「n % 3 == 0」のチェックだけで、O(1) の定数時間で回答を得ることができます。このように、数値の持つ性質を数学的に捉えることで、ナイーブな全探索よりもはるかに効率的なアルゴリズムを実装できるのがポイントです。