C++で1からNまでの範囲に含まれる「0」の桁を持つ数を数える方法

整数 N が与えられたとき、[1, N] の範囲内に存在する「桁に 0 を含む数」を見つけることが目標です。

この問題は、10 から N までの数を順番に走査することで解決できます(1〜9 は一桁の数なのでチェックする必要がありません)。各数値に対して while ループを使い、一桁ずつ確認していきます。もし 0 の桁が見つかればカウントを増やして次の数へ進み、見つからなければ数を 10 で割りながら次の桁を調べます。これを数値が 0 より大きい間繰り返します。

具体例で理解しよう

例1

入力

N = 11

出力

1 から N までの範囲で 0 を桁に持つ数: 1

解説

i = 10 から i <= 11 まで走査すると、
0 を桁に持つのは 10 のみです。[1, 9] の範囲はチェック不要です。

例2

入力

N = 100

出力

1 から N までの範囲で 0 を桁に持つ数: 10

解説

10, 20, 30, 40, 50, 60, 70, 80, 90, 100。
合計 10 個の数が 0 を桁に含んでいます。

プログラムのアプローチ

• 整数 N を受け取ります。
• 関数 haveZero(int n) が n を引数として受け取り、0 を桁に持つ数の個数を返します。
• カウント用の変数 count を初期値 0 で宣言します。
• for ループを使い、i = 10 から i = n までの範囲を走査します。
• 各数値 num = i について、while ループで num % 10 == 0 かどうかを判定します。条件を満たさない場合は num を 10 で割って次の桁へ移り、num > 0 の間これを繰り返します。
• 条件を満たした場合はそれ以上のチェックを打ち切り、count をインクリメントして while ループを抜けます。
• すべてのループが終了した時点で、count には 1 から N までの範囲で 0 を桁に持つ数の総数が格納されています。
• 最後に count を結果として返します。

C++ 実装コード

#include <bits/stdc++.h>
using namespace std;
int haveZero(int n){
    int count = 0;
    for (int i = 1; i <= n; i++) {
        int num = i;
        while(num>1){
            int digit=num%10;
            if (digit == 0){
                count++;
                break;
            }
            else
              { num=num/10; }
        }
    }
    return count;
}
int main(){
    int N = 200;
    cout <<"Numbers from 1 to N with 0 as digit: "<<haveZero(N);
    return 0;
}

実行結果

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

Numbers from 1 to N with 0 as digit: 29

N = 200 の場合、1 から 200 までの間に 0 を桁として含む数は 29 個あることがわかります。このアルゴリズムの計算量は O(N × 桁数) であり、シンプルながら効率的な実装となっています。