【C++】数字根がXとなるN番目の正の整数を求める方法

問題概要

この問題では、2つの整数値 N と X が与えられます。求めるのは、「数字根（デジタルルート）が X となる正の整数のうち、N 番目の数」を計算するプログラムです。

数字根（Digital Root）とは、ある数の各桁の合計を計算し、その結果が1桁になるまで同じ操作を繰り返すことで得られる、1桁の正の整数のことです。

具体例で理解しよう

入力

N = 5, X = 4

出力

40

この例では、数字根が4となる正の整数は「4, 13, 22, 31, 40, …」という順に現れるため、その5番目の値である「40」が答えになります。

解法①：全探索によるシンプルな方法

最も基本的な解法は、1から順に数を調べながら、数字根が X と一致する数をカウントしていく方法です。各数値について数字根を計算し、X と等しければカウンターを増やします。カウンターが N に到達した時点の数値が答えとなります。

実装例

#include <iostream>
using namespace std;
int calcDigitalRoot(int num) {
    int digitSum = 1000, number = num;
    while (digitSum >= 10) {
        digitSum = 0;
        while (number > 0) {
            digitSum += number % 10;
            number /= 10;
        }
        number = digitSum;
    }
    return digitSum;
}
int calcNthDigitalRoot(int X, int N) {
    int countDigitalRootVals = 0;
    for (int i = 1; countDigitalRootVals < N; ++i) {
        int digitalRoot = calcDigitalRoot(i);
        if (digitalRoot == X) {
            ++countDigitalRootVals;
        }
        if (countDigitalRootVals == N)
            return i;
    }
    return -1;
}
int main(){
    int X = 4, N = 5;
    cout<<N<<"th positive number whose digital root is "<<X<<" is "<<calcNthDigitalRoot(X, N);
    return 0;
}

出力

5th positive number whose digital root is 4 is 40

この方法は確実に正しい答えを返しますが、N が大きくなるほど計算時間が線形に増加するため、効率の面では不利です。

解法②：数式を使った効率的な方法

数字根には重要な性質があります。数字根が X となる数は、必ず「X, X+9, X+18, X+27, …」のように9個おきに出現するということです。これは「9で割った余りが等しい数同士は数字根も等しくなる」という性質に基づいています。

したがって、数字根が X となる N 番目の数は、次の直接的な公式で一発計算できます。

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

この公式を使えば、ループ処理が不要となり、O(1) の定数時間で答えを求められます。

実装例

#include <iostream>
using namespace std;
int calcNthDigitalRoot(int X, int N) {
    int nthNumber = (((N - 1) * 9) + X);
    return nthNumber;
}
int main() {
    int X = 4, N = 12;
    cout<<N<<"th positive number whose digital root is "<<X<<" is "<<calcNthDigitalRoot(X, N);
    return 0;
}

出力

12th positive number whose digital root is 4 is 103

まとめ

数字根が X となる N 番目の正の整数は、公式「(N − 1) × 9 + X」を使うことで即座に求められます。全探索でも解くことはできますが、数式ベースの解法は計算量が一定であり、競技プログラミングや技術面接ではこちらのアプローチが強く推奨されます。