นับจำนวน N หลักที่มีเลข 0 จำนวนคี่หลักใน C++

เราได้รับตัวเลข N เป้าหมายคือหาจำนวนตัวเลข N หลัก (รวม leading zeros) ที่มีเลข 0 จำนวนคี่หลัก

ตัวอย่าง

อินพุต: N = 3

เอาต์พุต: 244

คำอธิบาย: ตัวเลข 3 หลัก 000 ถึง 999 ที่มี 0 จำนวนคี่หลัก

อินพุต: N = 5

เอาต์พุต: 33616

แนวทางการแก้ปัญหา (คณิตศาสตร์)

• ตัวเลข N หลักทั้งหมด (รวม leading zeros): T = 10N
• ตัวเลข N หลักที่มี 0 จำนวนคู่: E = 10N - 8N (derive จาก generating function)
• ตัวเลขที่มี 0 จำนวนคี่: O = (T - E) / 2 = (10N - (10N - 8N)) / 2 = 8N / 2

สรุป: Count = (10N - 8N) / 2

การนำไปใช้ (Implementation)

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

int count_odd(int N) {
    long long total = pow(10, N);
    long long even = pow(8, N);
    long long odd = (total - even) / 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

หมายเหตุ: ควรใช้ long long และ fast exponentiation เพื่อป้องกัน overflow และเพิ่มความแม่นยำ