ইনপুট হিসাবে একটি সংখ্যা এবং একটি যোগফল সম্বলিত একটি স্ট্রিং স্ট্র দেওয়া হয়েছে। লক্ষ্য হল str পর্যন্ত সংখ্যা খুঁজে বের করা যেখানে মোট সংখ্যার সমষ্টি রয়েছে।
আসুন উদাহরণ দিয়ে বোঝা যাক।
উদাহরণস্বরূপ
ইনপুট - N=”110” যোগফল=5
আউটপুট - প্রদত্ত অঙ্কের যোগফলের সাথে N এর থেকে ছোট বা সমান সংখ্যাগুলির সংখ্যা হল:7
ব্যাখ্যা - 110 পর্যন্ত যে সংখ্যাগুলির যোগফল 5 এর সমান তা হল :-
5, 14, 23, 32, 41, 50 এবং 104৷
ইনপুট - N=”1000” যোগফল=3
আউটপুট - প্রদত্ত অঙ্কের যোগফলের সাথে N এর থেকে ছোট বা সমান সংখ্যার সংখ্যা হল:10
ব্যাখ্যা - 1000 পর্যন্ত যে সংখ্যাগুলির যোগফল 3 এর সমান অঙ্ক আছে তা হল :-
3, 12, 21, 30, 102, 111, 120, 201, 210 এবং 300৷
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
এই পদ্ধতিতে আমরা অ্যারে অ্যারে [18][2][162] সংখ্যার যোগফল এবং তাদের সংখ্যা সংরক্ষণ করতে ডায়নামিক প্রোগ্রামিং ব্যবহার করব। এখানে 18 হল সর্বাধিক 18 ডিজিটের সংখ্যার জন্য, 2 হল 0 এবং 1 মানের জন্য। এবং 162 হল সর্বাধিক সম্ভাব্য যোগফলের জন্য যদি সমস্ত 18 সংখ্যা 9 হয় ( 18*9=162 )।
উপাদান arr[i][j][k] এর মান এমন সংখ্যার গণনার প্রতিনিধিত্ব করে যার প্রথম i সংখ্যা বিবেচনায় নেওয়া হয় এবং j হল 0 বা 1 তার উপর ভিত্তি করে যে i সংখ্যা বর্তমান নির্মিত সংখ্যাটি প্রথম i সংখ্যার সংখ্যার চেয়ে কম বা বেশি N. (যদি N 123 হয় এবং i 2 হয় তাহলে আমরা পরীক্ষা করব যে 2 সংখ্যার সংখ্যা সমান বা 12 এর বেশি। যদি 12 এর সমান হয় তাহলে j হবে 1 আর j হবে 0 arr[i][j][k] ]) সূচক k হবে arr[i][j][k] এ i সংখ্যার সমষ্টি।
যদি i=N এর সংখ্যা এবং k=ইনপুট যোগফল হয় তাহলে ফলাফল হবে 1 অন্য 0।
পরবর্তী সংখ্যা ( i+1th ) পূরণের জন্য আমরা j চেক করব। যদি j 1 হয় তাহলে i-1 সংখ্যা N-এর i-1 সংখ্যার সমান তাই পরবর্তী অঙ্কের মান শুধুমাত্র N-এর 0 থেকে i+1 তম অঙ্কের মধ্যে থাকতে পারে <=N.
j যদি 0 হয় তাহলে i-1 ডিজিটের সংখ্যাটি N-এর i-1 ডিজিটের সংখ্যার চেয়ে কম। তাই আমরা পরবর্তী ডিজিটের (i+1 তম) অবস্থানের জন্য 0 থেকে 9 এর মধ্যে যেকোনো মান রাখতে পারি এবং এটি এখনও এর থেকে কম হবে এন.
শেষে চূড়ান্ত গণনা হিসাবে ফলাফল ফেরত দিন।
- সংখ্যা N এবং মোট অঙ্কের যোগফল হিসাবে প্রতিনিধিত্বকারী স্ট্রিং স্ট্র নিন৷
- অ্যারে অ্যারে নিন[18][2][162] এবং মেমসেট ব্যবহার করে -1 দিয়ে শুরু করুন।
- ফাংশন কাউন্ট_ডিজিট(int i, bool check, int temp, int total, string str, int size) পুনরাবৃত্তভাবে arr[][][] পূরণ করে এবং শেষে N এর থেকে ছোট বা সমান সংখ্যার সংখ্যা প্রদান করে অঙ্কের যোগফল।
- যদি i সংখ্যার বর্তমান সংখ্যা N সংখ্যার সমান হয় এবং বর্তমান যোগফল টেম্প ইনপুট যোগফলের সমান হয় তাহলে 1 ফেরত দিন অন্য 0 ফেরত দিন।
- গণনা নিন =arr[i][চেক][temp]। যদি এটি -1 না হয় তবে ফলাফল হিসাবে গণনা ফেরত দিন।
- অস্থায়ী ভেরিয়েবল চেক_2 ( bool ) এবং temp_2 নিন। (int)।
- লুপের জন্য 0 থেকে 9 পর্যন্ত সংখ্যা অতিক্রম করুন এবং চেক 1 বা 0 হলে তুলনা করুন। যদি 1 হয় তাহলে str[i] এর সাথে বর্তমান সংখ্যা ch-এর তুলনা করুন। যদি এটি বড় হয় তবে লুপটি ভেঙে দিন ( কিছুই করবেন না)।
- সেট check_2 =চেক || ch
- বর্তমান যোগফল হিসাবে temp_2 =temp + (ch - '0') সেট করুন।
- পুনরাবৃত্তভাবে অঙ্কের যোগফল গণনা করার জন্য গণনা_সংখ্যা (i + 1, check_2, temp_2, total, str, size) যোগ করুন।
- শেষে ফলাফল হিসাবে গণনা করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int arr[18][2][162];
int count_digits(int i, bool check, int temp, int total, ing 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
