C++で指定した数字dを含む数値をすべて検索する方法

問題の概要

数字 d と上限値 n が与えられたとき、0 から n までの範囲に存在する、数字 d を含むすべての数値を見つけることを考えます。

例えば、n = 20、d = 3 の場合、該当する数値は [3, 13] の2つになります。また、n = 100、d = 3 の場合は、3、13、23、30〜39、43、53 といった具合に、3 が現れるすべての数値が該当します。

解決のアプローチ

この問題は、各数値を文字列に変換することでシンプルに解決できます。手順は以下のとおりです。

1. 各数値を to_string() で文字列に変換する
2. 変換した文字列の中に、対象の数字 d が含まれているかを find() で確認する
3. 含まれていればその数値を出力し、含まれていなければ無視する

サンプルコード

#include<iostream>
using namespace std;

int getAllNumWithDigit(int n, int d) {
    string str = "";
    str += to_string(d);
    char ch = str[0];   // 対象の数字を文字として保持
    string p = "";
    p += ch;

    for (int i = 0; i <= n; i++) {
        str = "";
        str = str + to_string(i);   // 各数値を文字列に変換
        int index = str.find(p);    // 数字 d が含まれるか検索
        if (i == d || index != -1)
            cout << (i) << " ";
    }
}

int main() {
    int n = 100; int d = 3;
    getAllNumWithDigit(n, d);
}

実行結果

3 13 23 30 31 32 33 34 35 36 37 38 39 43 53 63 73 83 93

コードのポイント

この実装では、対象の数字 d をあらかじめ文字型（char）に変換して保持しておき、ループ内で各数値を文字列化してから find() 関数で部分一致を調べています。find() は該当する文字が見つかった場合にその位置を返し、見つからない場合は -1 を返すため、戻り値が -1 以外であれば「数字 d を含む数値」と判断できます。

計算量は、0 から n までの各数値に対して文字列変換と検索を行うため、O(n × log₁₀n) 程度となります。桁数が限られている実用的な範囲では十分に高速に動作します。

なお、文字列を使わずに各桁を % 10 と / 10 で分解して判定する方法もありますが、文字列変換を利用するこの方法はコードが簡潔で読みやすく、実装ミスも起こりにくいのが利点です。