การนับจำนวนในช่วงที่หลัก d เกิดขึ้นตรง K ครั้งใน C++

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

ตัวอย่าง

อินพุต - int start =10, int end =100, d =4 และ K =2

ผลลัพธ์ - การนับจำนวนในช่วงที่หลัก d เกิดขึ้นตรง K ครั้งคือ:1

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

ป้อนข้อมูล - int start =10, end =100, d =6 และ m =1

ผลลัพธ์ - การนับจำนวนในช่วงที่หลัก d เกิดขึ้นตรง K ครั้งคือ:1

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

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

• สร้างช่วงของตัวเลขจำนวนเต็มตั้งแต่ตัวแปรเริ่มต้นจนถึงสิ้นสุดตัวแปร และประกาศตัวแปร d และ k แล้วป้อนค่า ส่งข้อมูลไปยังฟังก์ชันเพื่อการประมวลผลต่อไป
• สร้างตัวแปรประเภทเวกเตอร์ สมมุติว่า vec
• เริ่มวนรอบในขณะที่ถึงค่าซึ่งเป็นค่าภายในตัวแปรเริ่มต้น ตอนนี้ ภายใน while ดันค่าเป็น val % 10 ไปยังเวกเตอร์ และตั้งค่า val เป็น val / 10
• เรียกใช้ฟังก์ชันย้อนกลับใน STL โดยส่ง vec.begin() และ vec.end() เป็นอาร์กิวเมนต์
• ตั้งค่าในอาร์เรย์เป็น -1 โดยใช้ memset
• คืนค่า set_total(0, 0, 0, vec) ซึ่งเป็นฟังก์ชันที่จะตรวจสอบว่าตัวเลขที่มีตำแหน่งคู่ d และหารด้วย m ลงตัวหรือไม่
• ภายในฟังก์ชัน set_total-:
  • ตรวจสอบว่าสถานที่ IF เท่ากับขนาดของเวกเตอร์ จากนั้นตรวจสอบ IF temp =k แล้วคืนค่า 1 หรือคืนค่า 0
  • ตรวจสอบ IF arr[place][temp][val][rem] not equals to -1 จากนั้นคืนค่าที่ arr[place][temp][val][rem].
  • ประกาศจำนวนตัวแปรเพื่อเก็บผลลัพธ์
  • ประกาศตัวแปร temp_2 และตั้งค่าเป็น 9 IF val เท่ากับ 1 ELSE ตั้งค่าด้วย vec[place]
  • เริ่มวนรอบ FOR จาก i ถึง 0 จนถึง temp_2 และตรวจสอบว่า IF i เท่ากับ d จากนั้นตรวจสอบว่า d note เท่ากับ 0 หรือ d เป็น 0 และ rem =1 แล้วเพิ่มผลรวม 1
  • ประกาศตัวแปรเป็น temp_2 และตั้งค่าเป็น val
  • ตรวจสอบว่า i น้อยกว่า vec[place] แล้วตั้งค่า temp_2 เป็น 1
  • ตั้งค่าการนับด้วยการเรียกซ้ำไปยังฟังก์ชัน set_total
  • กลับ arr[place][temp][val] =นับ

ตัวอย่าง

#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