C++で桁の合計が10になるn番目の数を求める方法

桁の合計が10になる数には、次のようなものがあります。

19, 28, 37, 46, 55, 64, 73, 82, 91 ...

この数列をよく観察すると、隣り合う数がすべて9ずつ増加していることがわかります。ただし、9ずつ増やしていく過程では、桁の合計が10にならない数も途中に現れます。それでも、桁の合計が10になる数はすべてこの方法で漏れなく見つけられます。

そこで、9ずつ増加させながら各数の桁の合計をチェックするループを作成すれば、n番目の数を効率よく求めることができます。以下に入力例と出力例を示します。

入力例

3
7

出力例

37
73

アルゴリズム

• 整数 n を初期化します。
• カウンターを0で初期化します。
• 19 から始まるループを作成します。
  • 現在の数の桁の合計が10であれば、カウンターを1増やします。
  • カウンターが n と等しくなったら、その時点の数を返します。
  • ループ変数を9ずつ増やします。

C++での実装

上記のアルゴリズムをC++で実装すると、次のようになります。

#include <bits/stdc++.h>
using namespace std;
int findNthNumber(int n) {
   int count = 0, i = 19;
   while (true) {
      int sum = 0;
      for (int number = i; number > 0; number = number / 10) {
         sum = sum + number % 10;
      }
      if (sum == 10) {
         count++;
      }
      if (count == n) {
         return i;
      }
      i += 9;
   }
   return -1;
}
int main() {
   int n = 7;
   cout << findNthNumber(7) << endl;
   return 0;
}

コードの解説

findNthNumber 関数では、19から始めて9ずつ増加させながら、各数の桁の合計を計算しています。桁の合計は、number % 10 で一の位を取り出し、number / 10 で桁を一つ下げる操作を繰り返すことで求めています。桁の合計が10になるたびにカウンターを増やし、カウンターが n に達した時点の数を返すというシンプルな仕組みです。

実行結果

上記のコードを実行すると、次の出力が得られます。

73