นับเลข 1 ในช่วง 1 ถึง N ใน C++ (Number of Digit One)

ภาพรวมปัญหา

นับจำนวนหลัก 1 ที่ปรากฏในตัวเลข 1 ถึง n

ตัวอย่าง

n = 15 → เลขที่มี 1: 1,10,11,12,13,14,15 → รวม 8 ตัว

วิธีแก้ปัญหา: คณิตศาสตร์ต่อหลัก (Digit DP แบบ iterative)

พิจารณาแต่ละหลัก (หน่วย, สิบ, ร้อย, ...)
สำหรับหลักที่มีค่า i (1, 10, 100, ...):
- a = n / i, b = n % i, x = a % 10
- x == 0: เพิ่ม (a/10)×i
- x == 1: เพิ่ม (a/10)×i + (b+1)
- x > 1: เพิ่ม (a/10 + 1)×i

โค้ด C++

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

class Solution {
public:
    int countDigitOne(int n) {
        int ret = 0;
        for (long long i = 1; i <= n; i *= 10) {
            int a = n / i;
            int b = n % i;
            int x = a % 10;
            if (x == 1) ret += (a / 10) * i + (b + 1);
            else if (x == 0) ret += (a / 10) * i;
            else ret += (a / 10 + 1) * i;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << (ob.countDigitOne(15));
}

ผลลัพธ์

8

การวิเคราะห์ความซับซ้อน

• เวลา: O(log n)
• พื้นที่: O(1)