C++で0を含むd桁の正の整数を数える方法

本記事では、数字の「0」を含むd桁の正の整数の個数を求めるプログラムについて、C++を用いて解説します。

問題概要

整数「d」が与えられます。「0」を少なくとも1つの桁として含むd桁の正の整数が全部でいくつあるかを数え、出力することが課題です。

アルゴリズム（考え方）

この問題は、すべての数を実際に列挙しなくても、組み合わせの考え方を使えば簡単に求められます。

• d桁の正の整数の総数：先頭の桁は1〜9の9通り、残りの(d−1)桁はそれぞれ0〜9の10通りなので、
  9 × 10^(d−1) 個
• 0をまったく含まないd桁の正の整数：各桁がすべて1〜9のいずれかになるため、
  9^d 個

したがって、0を含むd桁の正の整数の個数は、両者の差として次の式で表せます。

個数 = 9 × 10(d−1) − 9d = 9 × ( 10(d−1) − 9(d−1) )

実装例（C++）

#include<bits/stdc++.h>
using namespace std;
// 0を含むd桁の数を数える関数
int count_num(int d) {
    return 9*(pow(10,d-1) - pow(9,d-1));
}
int main(){
    int d = 1;
    cout << count_num(d) << endl;
    d = 2;
    cout << count_num(d) << endl;
    d = 4;
    cout << count_num(d) << endl;
    return 0;
}

出力結果

0
9
2439

計算例と補足

たとえば d＝2 の場合、10, 20, 30, …, 90 のように一の位が0となる2桁の数が9個存在し、出力と一致します。また d＝1 の場合、1〜9のどの数にも0は含まれないため、個数は0となります。

なお、pow関数は浮動小数点型（double）を返すため、dが大きくなると誤差が生じる可能性があります。実用上は戻り値をlong longなどの整数型にキャストするか、ループ処理でべき乗を計算する方法を採用すると安全です。