একটি ইন্টিজার রেঞ্জ দেওয়া আছে start থেকে end পর্যন্ত এবং দুটি ভেরিয়েবল k ও d। কাজ হল রেঞ্জে এমন সংখ্যাগুলোর সংখ্যা বের করা যাতে ডিজিট d ঠিক k বার উপস্থিত থাকে।
উদাহরণ
ইনপুট - int start = 10, int end = 100, d = 4, K = 2
আউটপুট - রেঞ্জে ডিজিট d ঠিক K বার থাকা সংখ্যার সংখ্যা: 1
ব্যাখ্যা - রেঞ্জ ১০ থেকে ১০০। ডিজিট ৪ ঠিক ২ বার থাকা সংখ্যা শুধু ৪৪। তাই কাউন্ট ১।
ইনপুট - int start = 10, end = 100, d = 6, m = 1
আউটপুট - রেঞ্জে ডিজিট d ঠিক K বার থাকা সংখ্যার সংখ্যা: 1
ব্যাখ্যা - রেঞ্জ ১০ থেকে ১০০। ডিজিট ৬ ঠিক ১ বার থাকা সংখ্যাগুলো: ১৬, ২৬, ৩৬, ৪৬, ৫৬, ৭৬, ৮৬, ৯৬ (মোট ৮টি)। ৬৬ গণনা নয় কারণ ৬ দুইবার আছে।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- ইন্টিজার রেঞ্জ, d এবং k ইনপুট নিয়ে ফাংশনে পাস করুন।
- একটি ভেক্টর
vecডিক্লেয়ার করুন। - হোয়াইল লুপে
val(start-এর মান) এর ডিজিটগুলোvec-এ পুশ করুন (val%10), তারপরval/=10। - STL-র
reverseফাংশন দিয়ে ভেক্টর উল্টান। - অ্যারে -1 দিয়ে ইনিশিয়ালাইজ করুন (
memset)। set_total(0, 0, 0, vec)রিটার্ন করুন যা চেক করবে নম্বরগুলোর ইভেন পজিশনে d আছে কিনা এবং m দিয়ে বিভাজ্য কিনা।set_totalফাংশনে:- যদি
place == vec.size()হয় তবেtemp == kহলে ১ রিটার্ন করুন অন্যথায় ০। - যদি
arr[place][temp][val][rem] != -1হয় তবে সেটি রিটার্ন করুন। countভেরিয়েবল ডিক্লেয়ার করুন।temp_2 = (val ? 9 : vec[place])।- i=0 থেকে temp_2 পর্যন্ত লুপ: যদি
i==dহয় তবে শর্ত অনুযায়ীtotal++। - রিকার্সিভ কল দিয়ে
countআপডেট করুন। arr[place][temp][val][rem] = countরিটার্ন করুন।
- যদি
উদাহরণ কোড
#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
