นับจำนวนในช่วง [START,END] ที่ไม่มีเลข 0 ผลรวมหลักเท่ากับ N และหาร M ลงตัวใน C++

ภาพรวมปัญหา

ให้ช่วง [START, END] และจำนวน N, M ต้องการนับจำนวนในช่วงที่:

1. ไม่มีหลักศูนย์ (no zero digits)
2. ผลรวมหลักเท่ากับ N
3. หาร M ลงตัว

ตัวอย่าง

Input: START=1, END=100, N=9, M=6

Output: 4

คำอธิบาย: 18, 36, 54, 72 — ผลรวมหลัก=9, หาร 6 ลงตัว, ไม่มีเลข 0

Input: START=100, END=200, N=10, M=2

Output: 4

คำอธิบาย: 118, 136, 154, 172

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

1. วนลูป i จาก START ถึง END
2. ถ้า i % M != 0 ข้าม (เพิ่มประสิทธิภาพ: ก้าวเป็น M)
3. คำนวณผลรวมหลัก และตรวจสอบว่ามีเลข 0 หรือไม่
4. ถ้าผลรวม = N และไม่มีเลข 0 ให้เพิ่ม count

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

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

int digitSum(int start, int end, int n, int m) {
    int count = 0;
    for (int i = start; i <= end; i++) {
        if (i % m != 0) continue;
        
        int num = i;
        int sum = 0;
        bool hasZero = false;
        
        while (num > 0) {
            int digit = num % 10;
            if (digit == 0) { hasZero = true; break; }
            sum += digit;
            num /= 10;
        }
        
        if (!hasZero && sum == n) count++;
    }
    return count;
}

int main() {
    int START = 1, END = 100, N = 9, M = 6;
    cout << "Count: " << digitSum(START, END, N, M);
    return 0;
}

ผลลัพธ์

Numbers with digit sum N and divisible by M: 4

การปรับปรุงประสิทธิภาพ

• เริ่มจากตัวคูณของ M แรกในช่วง: start = ((START + M - 1) / M) * M
• ก้าวเป็น M: for (int i = start; i <= END; i += M)
• ลดจำนวนรอบลูปจาก (END-START) เป็น (END-START)/M

โค้ดที่ปรับปรุงแล้ว

int digitSum_fast(int start, int end, int n, int m) {
    int count = 0;
    int first = ((start + m - 1) / m) * m; // ตัวคูณ m แรก ≥ start
    
    for (int i = first; i <= end; i += m) {
        int num = i, sum = 0;
        bool ok = true;
        while (num > 0) {
            int d = num % 10;
            if (d == 0) { ok = false; break; }
            sum += d;
            num /= 10;
        }
        if (ok && sum == n) count++;
    }
    return count;
}

ความซับซ้อน

• เวลา: O((END-START)/M × log₁₀END) — ประมาณ O((END-START)/M × จำนวนหลัก)
• พื้นที่: O(1)

ขยายเป็น Digit DP

สำหรับ END ใหญ่มาก (10¹⁸) ใช้ Digit DP นับจำนวนที่ตรงเงื่อนไขโดยไม่ต้องวนลูปทุกตัว