একটি স্ট্রিং str (যেটিতে একটি সংখ্যা রয়েছে) এবং একটি সম total ইনপুট হিসেবে দেওয়া আছে। লক্ষ্য হল str পর্যন্ত যেসব সংখ্যার ডিজিট সম total Leurs সমান, তাদের সংখ্যা বের করা।
উদাহরণ দিয়ে বোঝা যাক
ইনপুট - N="110", sum=5
আউটপুট - N-এর চেয়ে ছোট বা সমান এবং ডিজিট সম ৫ থাকা সংখ্যা: ৭
ব্যাখ্যা - ১১০ পর্যন্ত ডিজিট সম ৫ থাকা সংখ্যাগুলো: ৫, ১৪, ২৩, ৩২, ৪১, ৫০, ১০৪।
ইনপুট - N="1000", sum=3
আউটপুট - N-এর চেয়ে ছোট বা সমান এবং ডিজিট সম ৩ থাকা সংখ্যা: ১০
ব্যাখ্যা - ১০০০ পর্যন্ত ডিজিট সম ৩ থাকা সংখ্যাগুলো: ৩, ১২, ২১, ৩০, ১০২, ১১১, ১২০, ২০১, ২১০, ৩০০।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
ডাইনামিক প্রোগ্রামিং ব্যবহার করে সমস্যাটি সমাধান করা হয়। অ্যারে arr[18][2][162] ব্যবহার করা হয়। ১৮ = সর্বোচ্চ ১৮ ডিজিটের নম্বর, ২ = ০ বা ১ মান, ১৬২ = সর্বোচ্চ সম্ভাব্য সম (১৮×৯)।
arr[i][j][k]-এর মান উপস্থাপন করে: প্রথম i ডিজিট বিবেচনায় রেখে তৈরি সংখ্যাগুলোর কাউন্ট যেখানে j=০ বা ১ নির্ভর করে করেন্ট কনস্ট্রাক্টেড নম্বরের i-তম ডিজিট N-এর প্রথম i ডিজিট থেকে কম নাকি বেশি। (যদি N=123 এবং i=2 হয়, তবে চেক করা হয় ২-ডিজিট নম্বর ১২-এর সমান নাকি বেশি। সমান হলে j=১, অন্যথায় j=০)। k হলো i ডিজিটের সম।
যদি i=N-এর ডিজিট সংখ্যা এবং k=ইনপুট সম হয় তবে ফলাফল ১, অন্যথায় ০।
পরবর্তী ডিজিট (i+1th) পূরণের সময় j চেক করা হয়। j=১ হলে i-1 ডিজিট N-এর সমান, তাই পরের ডিজিট ০ থেকে N-এর i+1th ডিজিট পর্যন্ত হতে পারে। j=০ হলে i-1 ডিজিট N-এর চেয়ে ছোট, তাই পরের ডিজিট ০ থেকে ৯ যেকোনো হতে পারে।
- স্ট্রিং
str(N রিপ্রেজেন্ট করে) এবংtotalইনপুট নিন। - অ্যারে
arr[18][2][162]-1 দিয়ে ইনিশিয়ালাইজ করুন (memset)। - ফাংশন
count_digits(int i, bool check, int temp, int total, string str, int size)রিকার্সিভলি অ্যারে পূরণ করে এবং শেষে ফলাফল রিটার্ন করে। - যদি
i == sizeএবংtemp == totalহয় তবে ১ রিটার্ন করুন, অন্যথায় ০। count = arr[i][check][temp]। যদি -1 না হয় তবে রিটার্ন করুন।- টেম্পোরারি
check_2(bool) এবংtemp_2(int)। - ডিজিট ০ থেকে ৯ পর্যন্ত FOR লুপ: যদি
check==1হয় তবেch > str[i]হলে ব্রেক। check_2 = check || ch < str[i]।temp_2 = temp + (ch - '0')।- রিকার্সিভ কল দিয়ে
countআপডেট করুন। - চূড়ান্ত
countরিটার্ন করুন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int arr[18][2][162];
int count_digits(int i, bool check, int temp, int total, string str, int size) {
if (i == size) {
if (temp == total) return 1;
else return 0;
}
int count = arr[i][check][temp];
if (count != -1) return count;
count = 0;
bool check_2;
int temp_2;
for (char ch = '0'; ch <= '9'; ch++) {
if (!check) {
if (ch > str[i]) break;
}
check_2 = check || ch < str[i];
temp_2 = temp + (ch - '0');
count += count_digits(i + 1, check_2, temp_2, total, str, size);
}
return count;
}
int main() {
string str = "1101";
int size = str.size();
int total = 5;
memset(arr, -1, sizeof(arr));
cout << "Count of numbers smaller than or equal to N with given digit sum are: " << count_digits(0, 0, 0, total, str, size);
return 0;
}
উপরের কোড রান করলে নিচের আউটপুটটি পাওয়া যাবে:
আউটপুট
Count of numbers smaller than or equal to N with given digit sum are: 26
