C++で「x + 桁の合計 = n」を満たす数xを見つける方法

この記事では、ある整数 n が与えられたとき、「x + x の各桁の合計 = n」という条件を満たす数 x を求める問題を解説します。

例として、n = 21 の場合を考えてみましょう。このとき答えは x = 15 となります。なぜなら、15 の各桁の合計は 1 + 5 = 6 であり、15 + 6 = 21 となって、与えられた n と一致するからです。

解き方のアプローチ

この問題はシンプルな方法で解くことができます。1 から n まで順番に数を調べていき、それぞれの数について「その数自身 + 各桁の合計」が n と等しくなるかどうかを確認します。条件を満たす数が見つかった時点で処理を終了し、その値を返します。最後まで見つからなかった場合は -1 を返します。

C++での実装例

#include<iostream>
using namespace std;

// 各桁の合計を計算する関数
int getDigitSum(int n) {
    int sum = 0;
    while (n) {
        sum += n % 10;   // 最下位の桁を加算
        n /= 10;         // 桁を一つずらす
    }
    return sum;
}

// 条件を満たす数xを探す関数
int getNumber(int n) {
    for (int i = 0; i <= n; i++)
        if (i + getDigitSum(i) == n)
            return i;
    return -1;   // 見つからない場合
}

int main() {
    int n = 21;
    cout << "The value of x is: " << getNumber(n);
}

実行結果

The value of x is: 15

コードのポイント

getDigitSum 関数では、剰余演算（% 10）で最下位の桁を取り出し、10 で割ることで桁をずらしていくことで、全桁の合計を効率的に計算しています。

getNumber 関数では、0 から n まで線形探索を行い、条件「i + getDigitSum(i) == n」を満たす最初の数を返します。該当する数が存在しない場合は -1 を返す設計になっています。

このアルゴリズムの計算量は O(n × d) です（d は桁数）。n が非常に大きい場合は実行時間に注意が必要ですが、一般的な入力サイズであれば十分に高速に動作します。