C++で「数値とその各桁の合計がNに等しい数X」を見つける方法

このチュートリアルでは、「ある数値Xとその各桁の数字の合計を足した値が、与えられた数Nと等しくなる」という条件を満たす数Xを見つける方法を解説します。

解法のアイデア

考え方は非常にシンプルです。与えられた数Nの前後それぞれ100以内の範囲にある数をすべてチェックします。

制約として N ≤ 1,000,000,000(10億)であり、各桁の数字の合計は最大でも100程度にしかなりません。そのため、答えとなる数Xがこの範囲の外側に存在することはありません。

アルゴリズムの手順

• 対象となる数値Nを初期化します。
• 0から100まで繰り返すループを作成します。
  • n - i と n + i の値をそれぞれ取得します。
  • それぞれの数値について各桁の合計を計算し、元の数値に加算します。
  • 結果がNと一致した場合、その数値を出力します。

実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int digitsSum(int n) {
    int sum = 0;
    while (n) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

void findX(long int n) {
    bool is_found = false;
    for (int i = 0; i <= 100; i++) {
        long int valueOnLeft = abs(n - i) + digitsSum(abs(n - i));
        long int valueOnRight = n + i + digitsSum(n + i);
        if (valueOnLeft == n) {
            is_found = true;
            cout << abs(n - i) << " ";
        }
        if (valueOnRight == n) {
            is_found = true;
            cout << (n + i) << " ";
        }
    }
    if (!is_found) {
        cout << "No numbers found";
    }
    cout << endl;
}

int main() {
    int n = 89;
    findX(n);
    return 0;
}

実行結果

上記のプログラムを実行すると、以下の出力が得られます。

76

この例では、76 + 7 + 6 = 89 となり、条件を満たしていることが確認できます。

まとめ

本チュートリアルでは、各桁の数字との合計がNに等しい数Xを効率的に見つける方法を学びました。探索範囲を前後100に限定することで、高速に求解できる点が大きなポイントです。チュートリアルの内容について質問がある場合は、コメント欄でお気軽にお知らせください。