Đếm số trong một phạm vi mà chữ số d xuất hiện đúng K lần trong C ++

Chúng tôi được cung cấp với một phạm vi số nguyên bắt đầu từ một biến, giả sử bắt đầu cho đến khi biến kết thúc và một biến k và d. Nhiệm vụ là tính số chữ số d trong một phạm vi sao cho d xuất hiện đúng k lần.

Ví dụ

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

Đầu ra - Đếm số trong một phạm vi mà chữ số d xuất hiện đúng K lần là:1

Giải thích - Phạm vi bắt đầu từ 10 đến 100. Vì vậy, các số có thể có chữ số d, tức là 4 xảy ra chính xác k tức là 2 lần bằng 44, do đó số lượng là 1.

Đầu vào - int start =10, end =100, d =6 và m =1

Đầu ra - Đếm số trong một phạm vi mà chữ số d xuất hiện đúng K lần là:1

Giải thích - Phạm vi bắt đầu từ 10 đến 100. Vì vậy, các số có thể có chữ số d, tức là 4 xảy ra chính xác k tức là 1 lần là ở 16, 26, 36, 46, 56, 76, 86 và 96, do đó số lượng là 8. Chúng tôi sẽ không coi 66 vì 6 xảy ra nhiều hơn k lần.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Tạo một dải số nguyên bắt đầu từ đầu biến cho đến cuối biến và khai báo biến d và k và nhập các giá trị. Chuyển dữ liệu đến hàm để xử lý thêm.
Tạo một biến kiểu vectơ, giả sử vec.
Vòng lặp bắt đầu trong khi cho đến khi giá trị là giá trị bên trong biến bắt đầu. Bây giờ, trong khi đẩy giá trị là val% 10 vào vector và đặt val là val / 10.
Gọi hàm ngược trong STL bằng cách chuyển vec.begin () và vec.end () làm đối số cho nó.
Đặt các giá trị trong mảng là -1 bằng cách sử dụng memset.
Trả về set_total (0, 0, 0, vec) là một hàm sẽ kiểm tra xem các số có vị trí chẵn d và có chia hết cho m không
Bên trong hàm set_total-:
- Kiểm tra vị trí IF bằng với kích thước của vectơ, sau đó kiểm tra IF temp =k rồi trả về 1 hoặc trả về 0.
- Kiểm tra IF arr [place] [temp] [val] [rem] không bằng -1 rồi trả về giá trị tại arr [place] [temp] [val] [rem].
- Khai báo một số lượng biến để lưu trữ kết quả.
- Khai báo một biến temp_2 và đặt nó thành 9 IF val bằng 1 ELSE, hãy đặt nó bằng vec [place].
- Bắt đầu vòng lặp FOR từ i đến 0 cho đến nhiệt độ thứ 2 và kiểm tra NẾU i bằng d, sau đó kiểm tra NẾU d lưu ý bằng 0 HOẶC d là 0 VÀ rem =1 sau đó tăng tổng số 1
- Khai báo một biến là temp_2 và đặt nó thành val
- Kiểm tra NẾU tôi nhỏ hơn vec [place] rồi đặt temp_2 là 1
- Đặt số lượng bằng lệnh gọi đệ quy tới hàm set_total
- Trả lại arr [place] [temp] [val] =count.

Ví dụ

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

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Đầu ra

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