Đếm số trong khoảng không chứa quá K chữ số khác 0 bằng C++

Cho một khoảng nguyên từ start đến end và biến k. Nhiệm vụ: đếm số lượng số trong khoảng mà không có quá k chữ số khác 0.

Ví dụ

Đầu vào: start = 50, end = 100, K = 2

Đầu ra: Số lượng số thỏa mãn: 50

Giải thích: Khoảng 50-100. Tất cả số 2 chữ số không thể có quá 2 chữ số khác 0. Số 100 có 3 chữ số nhưng chỉ có 1 chữ số khác 0 → đếm = 50.

Đầu vào: start = 50, end = 100, K = 1

Đầu ra: Số lượng số thỏa mãn: 5

Giải thích: Các số không quá 1 chữ số khác 0: 50, 60, 70, 80, 90 → đếm = 5.

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

• Tạo dải số từ start đến end, khai báo k truyền cho hàm.
• Tạo vector vec lưu chữ số (tách %10, /10, reverse).
• Khởi tạo mảng arr với -1 bằng memset.
• Gọi check_val(0, 0, 0, vec) kiểm tra chữ số khác 0.
• Trong check_val:
  • Nếu place == vec.size() kiểm tra temp <= K trả về 1 else 0.
  • Nếu arr[place][temp][set_val] != -1 trả về giá trị đã lưu.
  • Duyệt chữ số 0-9, nếu i != 0 tăng temp_2, đệ quy tính toán.

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 
int arr[20][20][2]; 
int K; 

int check_val(int place, int temp, int set_val, vector<int> vec) { 
    if (place == vec.size()) { 
        if (temp <= K) return 1; 
        return 0; 
    } 
    if (arr[place][temp][set_val] != -1) { 
        return arr[place][temp][set_val]; 
    } 
    int count = 0; 
    int val = (set_val ? 9 : vec[place]); 
    for (int i = 0; i <= val; i++) { 
        int temp_2 = temp; 
        if (i != 0) temp_2++; 
        int temp_3 = set_val; 
        if (i < vec[place]) temp_3 = 1; 
        count += check_val(place + 1, temp_2, temp_3, vec); 
    } 
    return arr[place][temp][set_val] = count; 
} 

int Not_more_k(int val) { 
    vector<int> vec; 
    while (val) { 
        vec.push_back(val % 10); 
        val = val / 10; 
    } 
    reverse(vec.begin(), vec.end()); 
    memset(arr, -1, sizeof(arr)); 
    return check_val(0, 0, 0, vec); 
} 

int main() { 
    int start = 50, end = 100; 
    K = 2; 
    int count = Not_more_k(end) - Not_more_k(start); 
    cout << "Count of Numbers in Range where the number does not contain more than K non zero digits are: " << count; 
    return 0; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of Numbers in Range where the number does not contain more than K non zero digits are: 50