Đếm số thỏa mãn hiệu số với tổng chữ số không nhỏ hơn L trong C++

Cho một số N và một số L. Mục tiêu là tìm các số từ 1 đến N có hiệu giữa chính số đó và tổng chữ số của nó không nhỏ hơn L.

Nếu N=23, L=10 thì số lượng thỏa mãn là 4:

23-(2+3)=18, 22-(2+2)=18, 21-(2+1)=18, 20-(2+0)=18.
Tất cả thỏa mãn điều kiện.
Nhưng 19-(1+9)=9 < L, tương tự 18,17...1.

Ví dụ

Đầu vào - N=30, L=19

Đầu ra - Số thỏa mãn là 1

Giải thích - Chỉ 30 thỏa mãn: 30-(3+0)=27 > 19

Đầu vào - N=123330, L=5466

Đầu ra - Số thỏa mãn là 6841

Phương pháp sử dụng

Sử dụng tìm kiếm nhị phân tìm số đầu tiên thỏa mãn. Nếu số đó là num thì các số từ num+1 trở đi cũng thỏa mãn.

Nếu giá trị mid hiện tại thỏa mãn thì tất cả số từ mid đến end cũng thỏa mãn. Ta cộng end - mid + 1 vào count.

• Nhận num và L kiểu long
• Hàm Digit_sum(LL num) trả về tổng chữ số
• Khởi tạo total = 0, vòng lặp while cộng num%10, chia num/10 cho đến num > 0
• Hàm Less_than_L(LL num, LL L) trả về số lượng thỏa mãn
• Khởi tạo count = 0, binary search: start=1, end=num
• Tính mid = (start+end)/2
• Nếu mid - Digit_sum(mid) >= L: count += num - mid + 1, end = mid - 1
• Ngược lại: start = mid + 1
• Trả về count

Chương trình minh họa

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

typedef long long LL;

int Digit_sum(LL num) {
    LL total = 0;
    while (num > 0) {
        total += num % 10;
        num = num / 10;
    }
    return total;
}

LL Less_than_L(LL num, LL L) {
    LL count = 0;
    LL start = 1;
    LL end = num;
    while (start <= end) {
        LL temp = (end + start) / 2;
        LL temp_2 = temp - Digit_sum(temp);
        if (temp_2 >= L) {
            count = num - temp + 1;
            end = temp - 1;
        } else {
            start = temp + 1;
        }
    }
    return count;
}

int main() {
    LL num = 234516;
    LL L = 235;
    cout << "Số thỏa mãn hiệu với tổng chữ số không nhỏ hơn L là: " << Less_than_L(num, L);
    return 0;
}

Đầu ra

Số thỏa mãn hiệu với tổng chữ số không nhỏ hơn L là: 234267