นับจำนวนตัวเลขในช่วงที่เลข d ปรากฏทุก K ครั้งใน C++

เราได้รับช่วงจำนวนเต็มเริ่มจากตัวแปร start ถึงตัวแปร end และตัวแปร k และ d ภารกิจคือคำนวณจำนวนหลัก d ในช่วงที่ d ปรากฏทุก k ครั้ง

ตัวอย่าง

Input - int start = 10, int end = 100, d = 4 และ K = 2

Output - จำนวนตัวเลขในช่วงที่เลข d ปรากฏทุก K ครั้งคือ: 1

คำอธิบาย - ช่วงคือ 10 ถึง 100 ดังนั้น ตัวเลขที่เป็นไปได้ที่มีหลัก d คือ 4 ปรากฏทุก k คือ 2 ครั้ง คือ 44 เท่านั้น ดังนั้นจำนวนนับคือ 1

Input - int start = 10, end = 100, d = 6 และ m = 1

Output - จำนวนตัวเลขในช่วงที่เลข d ปรากฏทุก K ครั้งคือ: 1

คำอธิบาย - ช่วงคือ 10 ถึง 100 ดังนั้น ตัวเลขที่เป็นไปได้ที่มีหลัก d คือ 4 ปรากฏทุก k คือ 1 ครั้ง คือ 16, 26, 36, 46, 56, 76, 86 และ 96 ดังนั้นจำนวนนับคือ 8 เราจะไม่นับ 66 เพราะ 6 ปรากฏมากกว่า k ครั้ง

แนวทางที่ใช้ในโปรแกรมด้านล่าง

• สร้างช่วงจำนวนเต็มเริ่มจาก start ถึง end ประกาศตัวแปร d และ k และรับค่า ส่งข้อมูลให้ฟังก์ชันเพื่อประมวลผลต่อ
• สร้างตัวแปรประเภท vector คือ vec
• เริ่มลูป while จนกว่าค่าจะเป็นค่าภายในตัวแปร start ภายใน while ให้ push ค่า val % 10 เข้า vec และตั้ง val = val / 10
• เรียกฟังก์ชัน reverse ใน STL ส่ง vec.begin() และ vec.end()
• ตั้งค่าในอาร์เรย์เป็น -1 ด้วย memset
• คืนค่า set_total(0, 0, 0, vec) ซึ่งเป็นฟังก์ชันที่จะตรวจสอบว่าตัวเลขที่มีตำแหน่งคู่เป็น d และหารด้วย m ลงตัว
• ภายในฟังก์ชัน set_total:
  • ตรวจสอบ IF place == vec.size() แล้วตรวจสอบ IF temp == k คืนค่า 1 มิฉะนั้น 0
  • ตรวจสอบ IF arr[place][temp][val][rem] != -1 คืนค่าที่ arr[place][temp][val][rem]
  • ประกาศตัวแปร count เก็บผลลัพธ์
  • ประกาศตัวแปร temp_2 ตั้งเป็น 9 ถ้า val == 1 มิฉะนั้น vec[place]
  • เริ่มลูป FOR จาก i = 0 ถึง temp_2 ตรวจสอบ IF i == d แล้วตรวจสอบ IF d != 0 OR (d == 0 AND rem == 1) เพิ่ม total ขึ้น 1
  • ประกาศตัวแปร temp_2 ตั้งเป็น val
  • ตรวจสอบ IF i < vec[place] แล้ว temp_2 = 1
  • ตั้ง count ด้วยการเรียกฟังก์ชัน set_total แบบเรียกซ้ำ
  • คืนค่า arr[place][temp][val] = count

ตัวอย่าง

#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; 
}

หากเรารันโค้ดข้างต้น จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

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