นับตัวเลขในช่วงที่ไม่มีหลักไม่เป็นศูนย์เกิน K หลักใน C++

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

ตัวอย่าง

Input - int start = 50, end = 100 และ K = 2;

Output - จำนวนตัวเลขในช่วงที่ไม่มีหลักไม่เป็นศูนย์เกิน K หลักคือ: 50

คำอธิบาย - ช่วงคือ 50 ถึง 100 และ k = 2 ตามที่เห็น ตัวเลขทั้งหมดระหว่าง 50 ถึง 100 เป็นตัวเลข 2 หลัก ซึ่งทำให้เป็นไปไม่ได้ที่จะมีหลักไม่เป็นศูนย์เกิน 2 หลัก ยกเว้น 100 ที่เป็น 3 หลักแต่ก็มี 0 สองตัว ไม่เกินกว่านั้น ดังนั้นจำนวนนับคือ 50

Input - int start = 50, end = 100 และ K = 1;

Output - จำนวนตัวเลขในช่วงที่ไม่มีหลักไม่เป็นศูนย์เกิน K หลักคือ: 5

คำอธิบาย - ช่วงคือ 50 ถึง 100 และ k = 1 ตามที่เห็น ตัวเลขทั้งหมดระหว่าง 50 ถึง 100 เป็นตัวเลข 2 หลัก ดังนั้นตัวเลขที่มีหลักไม่เป็นศูนย์ไม่เกิน 1 คือ 50, 60, 70, 80 และ 90 ดังนั้นจำนวนนับคือ 5

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

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

ตัวอย่าง

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

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

ผลลัพธ์

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