एक स्ट्रिंग स्ट्रिंग को देखते हुए जिसमें एक संख्या और इनपुट के रूप में कुल योग होता है। लक्ष्य str तक की संख्याओं को खोजना है जिनमें अंकों का योग योग के बराबर हो।
आइए उदाहरणों से समझते हैं।
उदाहरण के लिए
इनपुट - एन =”110” योग=5
आउटपुट - दिए गए अंकों के योग के साथ N से छोटी या उसके बराबर संख्याओं की संख्या हैं:7
स्पष्टीकरण - 110 तक की संख्याएँ जिनके अंकों का योग 5 के बराबर है, वे हैं :-
5, 14, 23, 32, 41, 50 और 104.
इनपुट - एन ="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 होगा[i][j][k ] ) अनुक्रमणिका k, arr[i][j][k] में i अंकों का योग होगा।
अगर i=N के अंक और k=इनपुट योग तो परिणाम 1 और 0 होगा।
अगला अंक (i+1th) भरने के लिए हम j की जांच करेंगे। अगर j 1 है तो i-1 अंक N के i-1 अंकों के बराबर हैं, इसलिए अगले अंक में केवल 0 से i+1 के बीच का मान हो सकता है ताकि इसे <=N बनाया जा सके।
यदि j 0 है तो i-1 अंक संख्या N में i-1 अंक संख्या से कम है। इसलिए हम अगले अंक (i+1 th) स्थिति के लिए 0 से 9 के बीच कोई भी मान रख सकते हैं और यह अभी भी इससे कम होगा एन.
अंत में परिणाम को अंतिम गणना के रूप में लौटाएं।
- एक संख्या N और अंकों के योग के रूप में कुल का प्रतिनिधित्व करने वाली स्ट्रिंग लें।
- सरणी गिरफ्तार करें[18][2][162] और मेमसेट का उपयोग करके इसे -1 से प्रारंभ करें।
- फ़ंक्शन काउंट_डिजिट्स (इंट आई, बूल चेक, इंट टेम्प, इंट टोटल, स्ट्रिंग स्ट्र, इंट साइज) पुनरावर्ती रूप से एआर भरता है [] [] [] और अंत में दिए गए के साथ एन से छोटी या उसके बराबर संख्याओं की गणना करता है अंकों का योग।
- यदि अंकों की वर्तमान संख्या मैं एन के अंकों के बराबर है और वर्तमान योग अस्थायी इनपुट योग के बराबर है तो 1 और रिटर्न 0 लौटाएं।
- गिनती लें =गिरफ्तार करें [i] [जांचें] [अस्थायी]। यदि यह -1 नहीं है तो परिणाम के रूप में वापसी की गणना करें।
- अस्थायी चर चेक_2 (बूल) और temp_2 लें। (इंट) ।
- फॉर लूप का उपयोग करके अंकों को 0 से 9 तक पार करें और तुलना करें कि क्या चेक 1 या 0 है। यदि 1 है तो वर्तमान अंक ch की तुलना str[i] से करें। अगर यह बड़ा है तो लूप को तोड़ दें (कुछ न करें)।
- चेक_2 सेट करें =चेक करें || सीएच
- temp_2 =temp + (ch - '0') को वर्तमान योग के रूप में सेट करें।
- अंकों के योग की पुनरावर्ती गणना के लिए गणना करने के लिए count_digits(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