একটি ইন্টিজার রেঞ্জ দেওয়া আছে start থেকে end পর্যন্ত এবং একটি ভেরিয়েবল k। কাজ হল রেঞ্জে এমন সংখ্যাগুলোর সংখ্যা বের করা যাদের নন-জিরো ডিজিটের সংখ্যা k-এর চেয়ে বেশি নয়।
উদাহরণ
ইনপুট - int start = 50, end = 100, K = 2
আউটপুট - রেঞ্জে K-এর চেয়ে বেশি নন-জিরো ডিজিট না থাকা সংখ্যা: 50
ব্যাখ্যা - ৫০ থেকে ১০০ পর্যন্ত সব সংখ্যা ২-ডিজিট (১০০ বাদে ৩-ডিজিট কিন্তু তারও ২টি জিরো)। তাই সবই শর্ত পূরণ করে। কাউন্ট ৫০।
ইনপুট - int start = 50, end = 100, K = 1
আউটপুট - রেঞ্জে K-এর চেয়ে বেশি নন-জিরো ডিজিট না থাকা সংখ্যা: 5
ব্যাখ্যা - ৫০ থেকে ১০০ পর্যন্ত নন-জিরো ডিজিট ১ বা তার কম থাকা সংখ্যা: ৫০, ৬০, ৭০, ৮০, ৯০। কাউন্ট ৫।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- রেঞ্জ এবং k ইনপুট নিয়ে ফাংশনে পাস করুন।
- ভেক্টর
vecডিক্লেয়ার করুন। - হোয়াইল লুপে
val-এর ডিজিটগুলোvec-এ পুশ করুন এবং রিভার্স করুন। - অ্যারে -1 দিয়ে ইনিশিয়ালাইজ করুন (
memset)। check_val(0, 0, 0, vec)রিটার্ন করুন।check_valফাংশনে:- যদি
place == vec.size()হয় তবেtemp <= Kহলে ১ রিটার্ন করুন অন্যথায় ০। - যদি
arr[place][temp][set_val] != -1হয় তবে সেটি রিটার্ন করুন। count=0,val = (set_val ? 9 : vec[place])।- i=0 থেকে val পর্যন্ত লুপ:
temp_2 = temp; যদিi != 0হয় তবেtemp_2++।temp_3 = set_val; যদিi < vec[place]হয় তবেtemp_3=1। রিকার্সিভ কল দিয়েcountআপডেট করুন। 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
