นับจำนวนในช่วง [START,END] ที่ผลรวมหลักเท่ากับ Y ใน C++

ภาพรวมปัญหา

ให้ช่วง [START, END] และจำนวน Y ต้องการนับจำนวนในช่วงที่ผลรวมหลักเท่ากับ Y

ตัวอย่าง

Input: START=10, END=20, Y=4

Output: 1

คำอธิบาย: 13 (1+3=4)

Input: START=10, END=50, Y=5

Output: 5

คำอธิบาย: 14, 23, 32, 41, 50

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

1. ฟังก์ชัน digitSum(int start, int end, int y)
2. วนลูป i จาก START ถึง END
3. คำนวณผลรวมหลักของ i ด้วย while loop
4. ถ้าผลรวม == Y ให้เพิ่ม count

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

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

int digitSum(int start, int end, int y) {
    int count = 0;
    for (int i = start; i <= end; i++) {
        int num = i, sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        if (sum == y) count++;
    }
    return count;
}

int main() {
    int START = 100, END = 1000, Y = 5;
    cout << "Count: " << digitSum(START, END, Y);
    return 0;
}

ผลลัพธ์

Numbers such that digit sum is equal to Y: 15

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

สำหรับช่วงใหญ่ (END ≤ 10¹⁸) ใช้ Digit DP

หลักการ Digit DP

นับจำนวนใน [0, X] ที่ผลรวมหลัก = Y แล้วลบ: count(END) - count(START-1)

State: dp[pos][sum][tight] = จำนวนวิธีจากตำแหน่ง pos ที่ผลรวม = sum และ tight = ว่าถูกจำกัดโดย X หรือไม่

โค้ด Digit DP (Sketch)

long long dp[20][200][2];
string digits;
int target;

long long solve(int pos, int sum, bool tight) {
    if (pos == digits.size()) return sum == target;
    if (dp[pos][sum][tight] != -1) return dp[pos][sum][tight];
    
    int limit = tight ? digits[pos] - '0' : 9;
    long long ans = 0;
    for (int d = 0; d <= limit; d++) {
        ans += solve(pos + 1, sum + d, tight && (d == limit));
    }
    return dp[pos][sum][tight] = ans;
}

long long countUpTo(long long x, int y) {
    digits = to_string(x);
    target = y;
    memset(dp, -1, sizeof(dp));
    return solve(0, 0, true);
}

ความซับซ้อน