นับจำนวนหลักทั้งหมดจาก 1 ถึง N ใน C++

เราได้รับตัวเลข N เป้าหมายคือนับจำนวนหลักทั้งหมดของตัวเลขตั้งแต่ 1 ถึง N

ตัวอย่าง

อินพุต: N = 11

เอาต์พุต: 13

คำอธิบาย: 1-9: 9 หลัก, 10-11: 4 หลัก, รวม 13 หลัก

อินพุต: N = 999

เอาต์พุต: 2889

คำอธิบาย: 1-9: 9, 10-99: 180, 100-999: 2700, รวม 2889

แนวทางการแก้ปัญหา

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

แปลงแต่ละตัวเลขเป็นสตริง หาความยาว เรียกซ้ำสำหรับ num-1

int total_digits(int num) {
    string str = to_string(num);
    int length = str.length();
    if (num == 1) return 1;
    return length + total_digits(num - 1);
}

วิธีที่มีประสิทธิภาพ (O(log N))

สังเกตรูปแบบ: สำหรับแต่ละ 10ⁱ (1, 10, 100, ...) จำนวนหลักที่เพิ่มขึ้นคือ (N - i + 1)

int total_digits(int num) {
    int count = 0;
    for (int i = 1; i <= num; i *= 10) {
        count += (num - i + 1);
    }
    return count;
}

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

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

int total_digits(int num) {
    int count = 0;
    for (int i = 1; i <= num; i *= 10) {
        count += (num - i + 1);
    }
    return count;
}

int main() {
    int num = 20;
    cout << "Count of total number of digits from 1 to n are: " << total_digits(num);
    return 0;
}

เอาต์พุต

Count of total number of digits from 1 to n are: 31