Đếm số trong khoảng có chữ số d xuất hiện đúng K lần bằng C++

Cho một khoảng nguyên từ biến start đến end và các biến k và d. Nhiệm vụ là đếm số lượng số trong khoảng mà chữ số d xuất hiện chính xác k lần.

Ví dụ

Đầu vào: start = 10, end = 100, d = 4, K = 2

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

Giải thích: Khoảng 10 đến 100. Số có chữ số 4 xuất hiện đúng 2 lần là 44 → đếm = 1.

Đầu vào: start = 10, end = 100, d = 6, K = 1

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

Giải thích: Các số có chữ số 6 xuất hiện đúng 1 lần: 16, 26, 36, 46, 56, 76, 86, 96 (không tính 66 vì 6 xuất hiện 2 lần).

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

• Tạo dải số từ start đến end, khai báo d, k và truyền cho hàm xử lý.
• Tạo vector vec lưu các chữ số của số.
• Vòng lặp while tách chữ số: vec.push_back(val % 10), val = val / 10.
• Đảo ngược vector bằng reverse(vec.begin(), vec.end()).
• Khởi tạo mảng arr với -1 bằng memset.
• Gọi hàm set_total(0, 0, 0, vec) để kiểm tra.
• Trong set_total:
  • Nếu place == vec.size() kiểm tra temp == K trả về 1 else 0.
  • Nếu arr[place][temp][val][rem] != -1 trả về giá trị đã lưu.
  • Duyệt chữ số 0-9, nếu i == d tăng tổng nếu d != 0 hoặc d == 0 && rem == 1.
  • Đệ quy tính toán và lưu kết quả vào mảng DP.

Ví dụ mã nguồn

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

int set_total(int place, int temp, int val, int rem, vector<int> vec) { 
    if (place == vec.size()) { 
        if (temp == K) return 1; 
        return 0; 
    } 
    if (arr[place][temp][val][rem] != -1) { 
        return arr[place][temp][val][rem]; 
    } 
    int count = 0; 
    int temp_2 = (val ? 9 : vec[place]); 
    for (int i = 0; i <= temp_2; i++) { 
        int total = temp; 
        if (i == d) { 
            if (d != 0 || (!d && rem)) { 
                total++; 
            } 
        } 
        int total_2 = val; 
        if (i < vec[place]) { 
            total_2 = 1; 
        } 
        count += set_total(place + 1, total, total_2, rem || (i != 0), vec); 
    } 
    return arr[place][temp][val][rem] = count; 
} 

int occurrence_d(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 set_total(0, 0, 0, 0, vec); 
} 

int main() { 
    int start = 10; 
    int end = 100; 
    d = 4, K = 2; 
    int count = occurrence_d(end) - occurrence_d(start - 1); 
    cout << "Count of Numbers in a Range where digit d occurs exactly K times are: " << count; 
    return 0; 
}

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

Kết quả

Count of Numbers in a Range where digit d occurs exactly K times are: 1