C++で数字kを含む、またはkで割り切れるn番目の数を求める方法

問題の概要

2つの正整数 n と k が与えられ、「数字 k を含む数、または k で割り切れる数」のうち n 番目の数を求めます。ただし、k の範囲は 2〜9 とします。

例えば n = 15、k = 3 の場合、答えは 33 です。条件を満たす数は [3, 6, 9, 12, 13, 15, 18, 21, 23, 24, 27, 30, 31, 33] と並んでおり、これらはそれぞれ「3 という数字を含む」か「3 で割り切れる」数です。このうち n 番目にあたるのが 33 なので、出力は 33 となります。

解法のアプローチ

この問題は、シンプルなシミュレーション(全探索)で解くことができます。手順は以下の通りです。

1. 小さい数から順に整数を 1 つずつチェックする。
2. その数が数字 k を含んでいるか、または k で割り切れるかを判定する。
3. 条件を満たすたびにカウントを 1 増やし、カウントが n に達した時点の数を答えとして返す。

「数字 k を含むか」の判定は、数を 10 で割った余りで下一桁を取り出し、k と一致するかを確認する処理を桁数分だけ繰り返すことで実装できます。

C++による実装例

#include<iostream>
using namespace std;

// 数字 n の各桁に k が含まれているかを判定する関数
bool hasDigit(int n, int k) {
    while (n > 0) {
        int rem = n % 10;
        if (rem == k)
            return true;
        n = n / 10;
    }
    return false;
}

// 条件を満たす n 番目の数を求める関数
int countNumbers(int n, int k) {
    for (int i = k + 1, count = 1; count < n; i++) {
        if (hasDigit(i, k) || (i % k == 0))
            count++;
        if (count == n)
            return i;
    }
    return -1;
}

int main() {
    int n = 10, k = 2;
    cout << "Last number is " << countNumbers(n, k)
         << " before that the number contains " << k
         << " and multiple of " << k;
}

実行結果

Last number is 20 before that the number contains 2 and multiple of 2

コードの解説

hasDigit 関数

引数で受け取った整数を 10 で割った余り(下一桁)を順に取り出し、k と一致するかどうかを調べます。すべての桁を確認しても一致がなければ false を返します。

countNumbers 関数

k+1 から順に整数を調べていきます。最初の候補である k 自体は必ず条件を満たすため、count は 1 からスタートします。各数について hasDigit による桁の判定と k での剰余計算を行い、どちらかの条件を満たせば count を増やします。count が n に達した時点で、そのときの数を返します。

main 関数

n = 10、k = 2 として countNumbers を呼び出し、結果を標準出力に表示します。「2 を含む数または 2 の倍数」は 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 と続くため、10 番目の数は 20 になります。

計算量

• 時間計算量: O(N × D)。D は調べる数の桁数です。条件を満たす数が n 個見つかるまで順に走査するため、答えの大きさにほぼ比例します。
• 空間計算量: O(1)。追加のメモリはほとんど必要ありません。