C++で0を桁に含む最大d桁の正の整数の個数を求める方法

問題概要

桁数を表す整数 d が与えられます。このとき、「0」を少なくとも1つ桁に含み、最大 d 桁となる正の整数の個数を求めるのが目標です。つまり、1桁、2桁、3桁……d桁の正の整数の中から、0 を少なくとも1つ含むものをすべて数え上げます。

d桁の数の数え方

まず、d 桁の数のうち少なくとも1つの 0 を含むものの個数を求めてみましょう。例として d=3 の場合を考えます。少なくとも1つの 0 を含む3桁の数を作るには、次のような組み合わせが考えられます。

d1（百の位）に入る数字は 1〜9 ：9通り
d2（十の位）に入る数字は 0〜9 ：10通り
d3（一の位）に入る数字は 0〜9 ：10通り
作れる数の総数：9 × 10 × 10 = 9 × 10^2

一般化すると：
・d 桁の数の総数：9 × 10^(d-1)
・d 桁のうち 0 を一切含まない数：9^d 個
・したがって、少なくとも1つの 0 を含む d 桁の数の個数は
　9 × 10^(d-1) − 9^d = 9 × ( 10^(d-1) − 9^(d-1) )

具体例で確認してみましょう。

入力 − d=4

出力 − 0 を桁に含む最大 d 桁の正の整数の個数：2619

説明 − 各桁数における、0 を少なくとも1つ含む数の個数は次のとおりです。

1桁の数：0個
2桁の数：9個
3桁の数：171個
4桁の数：2439個
合計 = 9 + 171 + 2439 = 2619

入力 − d=1

出力 − 0 を桁に含む最大 d 桁の正の整数の個数：0

説明 − 1〜9 のいずれの数にも 0 という桁は含まれていないためです。

アプローチ①：素朴な方法（全桁を走査）

まずは for ループを使ったシンプルな方法から見ていきます。1桁から d 桁まで順番に走査し、先ほど導いた式で各桁数の個数を計算し、その都度合計に加算していきます。

• 桁数を表す整数 d を入力として受け取ります。

• 関数 total_count(int d) は、d 桁の数のうち少なくとも1つの 0 を含むものの個数を返します。

• temp = 9*(pow(10,d-1) - pow(9,d-1)); として個数を計算します。

• temp を返します。

• 関数 maximum_d(int d) は、最大桁数 d を受け取り、d 桁以下で少なくとも1つの 0 を含む数の個数を返します。

• ループで 1桁、2桁……と d 桁まで順に走査します。

• 各 i について total_count(i) を計算し、count に加算します。

• 最終的に全体の個数が得られます。

• count を結果として返します。

アプローチ②：効率的な方法（等比数列の活用）

このアプローチでは、各桁の個数の合計が等比数列（G.P.）の和になることに着目し、まとめて計算します。

解は Σ(i=1〜d) 9 × (10^(i-1) − 9^(i-1))
= {9 × (10^d − 1)} / (10 − 1) − {9 × (9^d − 1)} / (9 − 1)
= (10^d − 1) − (9/8) × (9^d − 1)

• d を最大桁数とします。

• 関数 maximum_d(int d) は、最大桁数 d を受け取り、d 桁以下で少なくとも1つの 0 を含む数の個数を返します。

• 上記の式をもとに、temp_1 = 9*((pow(10,d)-1)/9) を計算します。

• 同様に、temp_2 = 9*((pow(9,d)-1)/8) を計算します。

• count = temp_1 − temp_2 とします。

• count を結果として返します。

コード例（素朴な方法）

#include<bits/stdc++.h>
using namespace std;
int total_count(int d){
    int temp = 9*(pow(10,d-1) - pow(9,d-1));
    return temp;
}
int maximum_d(int d){
    int count = 0;
    for (int i=1; i<=d; i++){
        count = count + total_count(i);
    }
    return count;
}
int main(){
    int d = 5;
    cout<<"Count of positive integers with 0 as a digit and maximum 'd' digits are: "<<maximum_d(d) << endl;
    return 0;
}

出力

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

Count of positive integers with 0 as a digit and maximum 'd' digits are: 33570

コード例（効率的な方法）

#include<bits/stdc++.h>
using namespace std;
int maximum_d(int d){
    int temp_1 = 9*((pow(10,d)-1)/9);
    int temp_2 = 9*((pow(9,d)-1)/8);
    int count = temp_1 - temp_2;
    return count;
}
int main(){
    int d = 4;
    cout<<"Count of positive integers with 0 as a digit and maximum 'd' digits are: "<<maximum_d(d) << endl;
    return 0;
}

出力

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

Count of positive integers with 0 as a digit and maximum 'd' digits are: 2619

まとめ

素朴な方法では1桁から d 桁まで順に計算するため計算量は d に比例しますが、等比数列の和の公式を使う効率的な方法なら、d の値に関わらず定数回の演算で答えを求められます。大きな d を扱う場合は、後者のアプローチが有利です。ただし、実際の実装では桁数が大きくなると結果が int 型の範囲を超える可能性があるため、必要に応じて long long 型などの使用を検討してください。