C++で特定の数字を含まないn桁の数をカウントする方法

問題概要

本記事では、次のような問題をC++で解く方法を解説します。

整数 n(桁数)と特定の1桁の数字 digit が与えられます。このとき、「指定された数字をひとつも含まない n 桁の数」が全部でいくつ存在するかを求めるのがゴールです。

入力例と出力例

入力: n = 2, digit = 2
出力: 72

説明: 2桁の数(10〜99)のうち、数字「2」を含まないものは 10, 11, 13, 14, 15, 16, 17, 18, 19, 30, 31, 33, ... などです。十の位は「2」以外の8通り、一の位は「2」以外の9通りから選べるため、全体で 8 × 9 = 72 個となります。

入力: n = 3, digit = 3
出力: 648

説明: 3桁の数(100〜999)のうち、数字「3」を含まないものは、百の位が8通り、十の位と一の位がそれぞれ9通りずつなので、8 × 9 × 9 = 648 個となります。

アルゴリズムのアプローチ

ここでは、範囲内のすべての数を実際に調べる「全探索」のアプローチを採用します。手順は以下のとおりです。

• n と digit を整数変数として入力します。
• カウント処理を行う関数にこれらの変数を渡します。
• n 桁の数が取りうる最小値(min)と最大値(max)を求めます。例えば、2桁の数は最小値10から最大値99まで、3桁の数は最小値100から最大値999までです。
• min から max までforループを回します。
• ループ内では、各数値に対してwhile文を使い、下の桁から順に1桁ずつ取り出しながら、指定された digit が含まれているかどうかを判定します。
• digit がひとつも含まれていない数だけ、カウントを1増やします。

C++での実装例

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

// 特定の数字を含まないn桁の数をカウントする関数
int countNumbers(int n, int digit) {
    int count = 0;
    // n桁の数の最小値と最大値を計算
    int minValue = (int)(pow(10, n - 1));
    int maxValue = (int)(pow(10, n));
    // 最小値から最大値までループ
    for (int i = minValue; i < maxValue; i++) {
        int a = i;
        int flag = 0;
        // 各桁を下から順に調べる
        while (a > 0) {
            int r = a % 10;
            a = a / 10;
            if (r == digit) {
                flag++;
            }
        }
        // 指定した数字が含まれていなければカウントアップ
        if (flag == 0) {
            count++;
        }
    }
    return count;
}

int main() {
    int n = 2, digit = 2;
    cout << n << "桁の数のうち、" << digit << "を含まない数の個数は : "
         << countNumbers(n, digit);
    return 0;
}

実行結果

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

2桁の数のうち、2を含まない数の個数は :72

計算量と補足

• 時間計算量: O((max − min) × n)。調査対象の候補数 × 各数の桁数分の処理が必要になります。
• 空間計算量: O(1)。追加で必要なメモリは定数のみです。

なお、この問題は数学的な式でも解けます。先頭の桁は0にできないため、digit が0なら9通り、それ以外なら8通り。残りの n−1 桁はそれぞれ digit 以外の9通りから選べます。したがって、答えは (digit が0なら9、それ以外なら8) × 9ⁿ⁻¹ という式で、ループ処理なしに一瞬で求められます。大きな n を扱う場合はこちらの方法が効率的です。