C++で0が奇数個含まれるN桁の数を数える方法

整数 N が入力として与えられます。目的は、各桁に含まれる 0 の個数が奇数となる N 桁の数が全部でいくつあるかを求めることです。ここでは先頭の 0 も有効な桁として扱います。たとえば N=3 の場合、000、011、012、…、990 のような数もカウント対象に含まれます。

具体例を使って理解しましょう。

入力 − N=3

出力 − 0 が奇数個含まれる N 桁の数の個数 − 244

説明 − 3 桁の数は次のような並びになります。

最小は 000、続いて 011、012、013、014、…、最大は 990。

入力 − N=5

出力 − 0 が奇数個含まれる N 桁の数の個数 − 33616

説明 − 5 桁の数は次のような並びになります。

最小は 00000、続いて 00011、00012、00013、00014、…、最大は 99990。

プログラムで使用するアプローチ

まず、先頭の 0 を含む N 桁の数の総数を T = 10^N とします。次に、二項定理の性質を利用すると、「0 が偶数個含まれる数の個数」と「0 が奇数個含まれる数の個数」の差が 8^N になることが分かります。したがって、求めたい「0 が奇数個含まれる数」の個数は (T − 8^N) / 2 として計算できます。

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

• 関数 count_odd(int N) は N を受け取り、0 が奇数個含まれる N 桁の数の個数を返します。

• N 桁の数の総数は total = pow(10, N) で計算します。

• 偶数個の場合と奇数個の場合の個数の差は diff = pow(8, N) で計算します。

• 0 が奇数個含まれる数の個数は odd = (total − diff) / 2 となります。

• odd を「0 が奇数個含まれる N 桁の数の個数」として返します。

このアルゴリズムのポイント

すべての数を実際に列挙して 0 の個数を数える代わりに、数学的な性質を利用することで、pow の計算だけで即座に答えを求められる点が大きな魅力です。そのため N が大きくなっても高速に動作します。

例

#include <bits/stdc++.h>
using namespace std;
int count_odd(int N){
    int total = pow(10, N);
    int diff = pow(8, N);
    int odd = (total - diff) / 2;
    return odd;
}
int main(){
    int N = 4;
    cout<<"Count of Numbers with N digits which consists of odd number of 0's are: "<<count_odd(N);
return 0;
}

出力

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

Count of Numbers with N digits which consists of odd number of 0's are: 2952