Chúng tôi được cung cấp một phạm vi số nguyên bắt đầu từ biến, giả sử bắt đầu cho đến khi kết thúc biến và một biến k và nhiệm vụ là tính toán số lượng các số trong phạm vi sao cho các số không có nhiều hơn 'k' khác 0 chữ số.
Ví dụ
Đầu vào - int start =50, end =100 và K =2;
Đầu ra - Đếm số trong phạm vi mà số không chứa nhiều hơn K chữ số khác 0 là:50
Giải thích - Phạm vi bắt đầu từ 50 đến 100 và chúng ta được cho k là 2. Như chúng ta có thể thấy, tất cả các số từ 50 đến 100 đều có 2 chữ số nên không thể chứa nhiều hơn 2 chữ số 0 ngoại trừ số 100 là một số có 3 chữ số nhưng nó cũng sẽ có 2 số 0 không nhiều hơn số đó, do đó số lượng là 50.
Đầu vào - int start =50, end =100 và K =1;
Đầu ra - Đếm số trong phạm vi trong đó số không chứa nhiều hơn K khác 0
chữ số là:5
Giải thích - Phạm vi bắt đầu từ 50 đến 100 và chúng ta được cho k là 1. Như chúng ta thấy, tất cả các số từ 50 đến 100 đều có 2 chữ số nên các số có không quá 1 hoặc k là các chữ số khác 0 là 50 , 60, 70, 80 và 90 do đó số lượng là 5.
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 k và nhập 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ề check_val (0, 0, 0, vec), đây là một hàm sẽ kiểm tra xem các chữ số có phải là chữ số khác không hay không.
- Bên trong hàm check_val-:
- 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 NẾU arr [place] [temp] [set_val] không bằng -1 rồi trả về giá trị tại arr [place] [temp] [set_val].
- Khai báo biến để lưu trữ kết quả và đặt nó thành 0.
- Khai báo một biến val và đặt nó thành 9 IF set_val bằng 1 ELSE đặt nó thành i ++
- Bắt đầu vòng lặp FOR từ 0 cho đến giá trị val
- Bên trong vòng lặp, đặt temp_2 làm tạm thời và kiểm tra NẾU 1 không bằng 0, sau đó tăng giá trị của temp_2 lên 1 và đặt temp_3 là set_val và kiểm tra tôi nhỏ hơn vec [place] rồi đặt temp_3 là 1
- Đặt giá trị của count dưới dạng lệnh gọi đệ quy cho hàm check_val (place + 1, temp_2, temp_3, vec)
- Trả về arr [place] [temp] [set_val] bằng số lượng.
Ví dụ
#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;
} 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 Range where the number does not contain more than K non zero digits are: 50