นับจำนวนจำนวนเต็มบวกที่มีเลข 0 และมีหลักสูงสุด d หลักใน C++

เราได้รับตัวเลข d ซึ่งแทนจำนวนหลัก เป้าหมายคือการหาจำนวนจำนวนเต็มบวกที่มีเลข 0 อยู่ในตัวเลข และมีจำนวนหลักสูงสุด d หลัก นั่นคือ นับจำนวนทั้งหมดของตัวเลข 1 หลัก, 2 หลัก, 3 หลัก... จนถึง d หลัก ที่มีเลข 0 อย่างน้อย 1 ตัว

หลักการคำนวณ

สำหรับตัวเลข d หลักที่มีเลข 0 อย่างน้อย 1 ตัว:

• หลักแรก (d1) สามารถเป็น 1-9 ได้: 9 วิธี
• หลักที่เหลือ (d2 ถึง dd) สามารถเป็น 0-9 ได้: 10 วิธีต่อหลัก
• ตัวเลข d หลักทั้งหมด: 9 × 10d-1
• ตัวเลข d หลักที่ไม่มีเลข 0 เลย: 9d
• ตัวเลข d หลักที่มีเลข 0 อย่างน้อย 1 ตัว: 9 × 10d-1 - 9d = 9 × (10d-1 - 9d-1)

ตัวอย่าง

อินพุต: d = 4

เอาต์พุต: 2619

คำอธิบาย:

1 หลัก: 0
2 หลัก: 9
3 หลัก: 171
4 หลัก: 2439
รวม = 9 + 171 + 2439 = 2619

อินพุต: d = 1

เอาต์พุต: 0

คำอธิบาย: 1 ถึง 9 ไม่มีตัวเลขไหนมีเลข 0

วิธีการแก้ปัญหา

วิธีแบบง่าย (Naive Approach)

ใช้ลูป for วนตั้งแต่ 1 หลัก ถึง d หลัก คำนวณจำนวนด้วยสูตรข้างต้น และบวกสะสม

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

int total_count(int d) {
    int temp = 9 * (pow(10, d-1) - pow(9, d-1));
    return temp;
}

int maximum_d(int d) {
    int count = 0;
    for (int i = 1; i <= d; i++) {
        count = count + total_count(i);
    }
    return count;
}

int main() {
    int d = 5;
    cout << "Count of positive integers with 0 as a digit and maximum 'd' digits are: " << maximum_d(d) << endl;
    return 0;
}

เอาต์พุต: 33570

วิธีที่มีประสิทธิภาพ (Efficient Approach)

สังเกตว่าสูตรเป็นอนุกรมเรขาคณิต (G.P.) สามารถลดรูปได้เป็น:

Count = (10d - 1) - (9/8) × (9d - 1)

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

int maximum_d(int d) {
    int temp_1 = 9 * ((pow(10, d) - 1) / 9);
    int temp_2 = 9 * ((pow(9, d) - 1) / 8);
    int count = temp_1 - temp_2;
    return count;
}

int main() {
    int d = 4;
    cout << "Count of positive integers with 0 as a digit and maximum 'd' digits are: " << maximum_d(d) << endl;
    return 0;
}

เอาต์พุต: 2619