นับจำนวนที่มีเลข 0 อยู่ในตัวเลขในช่วง [1,N] ใน C++

ภาพรวมปัญหา

ให้จำนวน N ต้องการนับจำนวนใน [1, N] ที่มีหลัก 0 อย่างน้อย 1 หลัก

ตัวอย่าง

Input: N = 11

Output: 1

คำอธิบาย: 10 มีเลข 0

Input: N = 100

Output: 10

คำอธิบาย: 10,20,30,40,50,60,70,80,90,100

แนวทางแก้ปัญหา (Brute Force)

1. วนลูป i = 10 ถึง N (1-9 ไม่มี 0)
2. แยกหลักด้วย while loop ตรวจสอบ digit == 0
3. ถ้าเจอ 0 ให้เพิ่ม count และ break

โค้ดตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int haveZero(int n) {
    int count = 0;
    for (int i = 10; i <= n; i++) { // เริ่มที่ 10
        int num = i;
        while (num > 0) {
            if (num % 10 == 0) {
                count++;
                break;
            }
            num /= 10;
        }
    }
    return count;
}

int main() {
    int N = 200;
    cout << "Numbers with 0 as digit: " << haveZero(N);
    return 0;
}

ผลลัพธ์

Numbers from 1 to N with 0 as digit: 29

แนวทางคณิตศาสตร์ O(log N) — Complementary Counting

นับจำนวนที่ ไม่มีเลข 0 แล้วลบออกจาก N

จำนวน k หลักที่ไม่มี 0: 9ᵏ (แต่ละหลักเลือก 1-9 ได้ 9 ทางเลือก)

สูตรสำหรับ N = 10ᵏ - 1 (เช่น 9, 99, 999...)

ไม่มี 0 = 9 + 9² + ... + 9ᵏ = 9(9ᵏ - 1)/8

มี 0 = N - ไม่มี 0

อัลกอริทึมทั่วไป (Digit DP / Greedy)

int countWithZero(int n) {
    string s = to_string(n);
    int len = s.length();
    int countNoZero = 0;
    
    // นับจำนวนที่ไม่มี 0 และ < n
    for (int i = 1; i < len; i++) {
        countNoZero += pow(9, i); // i-digit numbers no zero
    }
    
    // นับจำนวน len หลักที่ไม่มี 0 และ ≤ n
    for (int i = 0; i < len; i++) {
        int digit = s[i] - '0';
        int remaining = len - i - 1;
        
        // เลือกหลักนี้ < digit (และ > 0)
        int choices = max(0, digit - (i == 0 ? 1 : 0)); // leading digit ไม่เป็น 0
        countNoZero += choices * pow(9, remaining);
        
        if (digit == 0) break; // ไม่สามารถต่อได้แล้ว
        if (i == len - 1) countNoZero++; // n เองไม่มี 0
    }
    
    return n - countNoZero;
}

ความซับซ้อน

ข้อควรระวังในโค้ดต้นฉบับ

• ลูป while เงื่อนไข `num > 1` ควรเป็น `num > 0` (แต่ผลลัพธ์ถูกต้องเพราะ num=1 จะไม่มี digit 0)
• เริ่มลูปที่ 10 ถูกต้อง (1-9 ไม่มี 0)