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

整数Nが入力として与えられ、「各桁に現れる0の個数が偶数個であるN桁の数」が全部でいくつあるかを求めるのがこの問題の目的です。ここで扱う数には先頭の0も含まれます。たとえばN=3の場合、001、002、003…010…といった数もすべて対象になります。

具体例で理解する

入力例1

入力：N=4

出力：0が偶数個含まれるN桁の数の個数は 7047

説明：4桁のすべての数は次のようになります。

最小値は0000、その次は0011、0012、0013、0014……と続き、最大値は9900です。

入力例2

入力：N=5

出力：0が偶数個含まれるN桁の数の個数は 66383

説明：5桁のすべての数は次のようになります。

最小値は00001、その次は00002、00003、00004……と続き、最大値は99900です。

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

まず、N桁の数の総数Tを求めます。これは T = 10^N − 1 です（000…0という0のみの並びを除外します）。次に、0が奇数個含まれるN桁の数の個数Oを O = 10^N − 8^N として計算します。すると、求めたい「0が偶数個含まれる数」の個数は残りの T − O ÷ 2 で表せます。

補足すると、各桁に入る数字は0〜9の10通りなので、長さNの数字列全体は10^N通り存在します。二項定理から、0が偶数個含まれる列の数は (10^N + 8^N) ÷ 2、奇数個含まれる列の数は (10^N − 8^N) ÷ 2 と導けます。コードでは計算の都合上、奇数側を10^N − 8^Nとして求めておき、後から2で割る形にしています。

アルゴリズムの手順

• 整数Nを入力として受け取ります。
• 関数count_even(int N)がNを受け取り、0が偶数個含まれるN桁の数の個数を返します。
• N桁の数の総数は total = pow(10, N) - 1 で求めます。
• 0が奇数個含まれるN桁の数の総数は odd = pow(10, N) - pow(8, N) で求めます。
• 残りの0が偶数個含まれる数は even = total - odd / 2 で求めます。
• evenを「0が偶数個含まれるN桁の数の個数」として返します。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
int count_even(int N){
    int total = pow(10, N) - 1;
    int odd = pow(10, N) - pow(8, N);
    int even = total - odd / 2;
    return even;
}
int main(){
    int N = 3;
    cout<<"0が偶数個含まれるN桁の数の個数: "<<count_even(N);
    return 0;
}

出力

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

0が偶数個含まれるN桁の数の個数: 755