【C++】デジタルルート（繰り返し桁和）がNとなるM番目の数を求める方法

問題概要

この問題では、2つの正の整数 N と M が与えられます。求めるのは、「ある数の各桁の和を繰り返し計算して1桁になるまで処理した結果（デジタルルート）が N と等しくなる」ような数のうち、M番目の数です。

例えば、入力として N = 4、M = 6 が与えられた場合、出力は 49 となります。

その理由を見てみましょう。49 の各桁の和は 4 + 9 = 13、さらに 1 + 3 = 4 となり、最終的に 4 になります。デジタルルートが 4 となる数は 4, 13, 22, 31, 40, 49 … と公差 9 で続いていくため、6番目の数は 49 となるのです。

解法アプローチ

最も単純な解法は、すべての数を順番に調べ、デジタルルートが N と一致する数をカウントしていき、M個目に到達した時点でその数を返すというものです。

しかし、この問題にはより効率的な数式を使った解法が存在します。デジタルルートが N となる数は、N, N+9, N+18, … というように公差 9 の等差数列をなすため、M番目の数は次の式で一発的に求められます。

M番目の数 = (M − 1) × 9 + N

この式により、数を順に走査する必要がなくなり、O(1) の計算量で答えを得ることができます。

解法の実装プログラム

以下は、上記の式を使って問題を解く C++ プログラムの例です。

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

int main() {

    int n = 4, m = 6;
    int mNumber = (m - 1) * 9 + n;
    cout<<m<<"-th number whose repeated sum of digits of a number is "<<n<<" is "<<mNumber;
    return 0;
}

出力

6-th number whose repeated sum of digits of a number is 4 is 49

このように、公式を活用することで繰り返し処理を行わずに、目的の M 番目の数を簡単かつ高速に求めることができます。