นับจำนวนใน [1,N] ที่ผลต่างกับผลรวมหลักมากกว่า D ใน C++

ภาพรวมปัญหา

ให้ N และ D ต้องการนับจำนวนใน [1, N] ที่ (ตัวเลข - ผลรวมหลัก) > D

ตัวอย่าง

Input: N = 15, D = 5

Output: 6

คำอธิบาย: 10,11,12,13,14,15 — ผลต่างคือ 9,9,9,9,9,9 (>5)

Input: N = 20, D = 10

Output: 1

คำอธิบาย: 20 - 2 = 18 > 10

ข้อสังเกตสำคัญ

สำหรับจำนวน x ที่มีหลัก d_k...d_1d_0:

• x = Σ dᵢ × 10ⁱ
• ผลรวมหลัก = Σ dᵢ
• x - sumDigits = Σ dᵢ × (10ⁱ - 1) = Σ dᵢ × (9, 99, 999, ...)
• ค่านี้จะหาร 9 ลงตัวเสมอ และเพิ่มขึ้นตามจำนวนหลัก

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

1. วนลูป i = 1 ถึง N
2. คำนวณผลรวมหลัก
3. ถ้า i - sumDigits > D ให้เพิ่ม count

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

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

int digitSum(int n, int d) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        int num = i, sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        if (i - sum > d) count++;
    }
    return count;
}

int main() {
    int N = 20, D = 8;
    cout << "Count: " << digitSum(N, D);
    return 0;
}

ผลลัพธ์

Numbers such that difference between number and its digit sum greater than specific value: 11

แนวทางที่มีประสิทธิภาพมากกว่า (Digit DP)

สำหรับ N ใหญ่ (≤ 10¹⁸) ใช้ Digit DP นับจำนวนที่ x - sumDigits(x) > D

State: dp[pos][sum][tight] — นับจำนวนวิธีสร้างตัวเลขจากตำแหน่ง pos

ข้อสังเกตเพิ่มเติม

• ฟังก์ชัน f(x) = x - sumDigits(x) เป็น non-decreasing
• f(x+1) - f(x) = 1 - (sumDigits(x+1) - sumDigits(x)) ≥ 0
• สามารถใช้ Binary Search หาจุดเริ่มต้นที่ f(x) > D ได้

ความซับซ้อน