एक स्ट्रिंग str दी गई है जिसमें एक संख्या है और एक योग total इनपुट के रूप में। लक्ष्य str तक की उन संख्याओं को ढूंढना है जिनके अंकों का योग total के बराबर है।
उदाहरणों से समझते हैं।
उदाहरण के लिए
इनपुट - N="110" sum=5
आउटपुट - दिए गए अंक योग वाली N से छोटी या बराबर संख्याओं की संख्या: 7
व्याख्या - 110 तक की संख्याएं जिनके अंकों का योग 5 के बराबर है :-
5, 14, 23, 32, 41, 50 और 104।
इनपुट - N="1000" sum=3
आउटपुट - दिए गए अंक योग वाली N से छोटी या बराबर संख्याओं की संख्या: 10
व्याख्या - 1000 तक की संख्याएं जिनके अंकों का योग 3 के बराबर है :-
3, 12, 21, 30, 102, 111, 120, 201, 210 और 300।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
इस दृष्टिकोण में हम डायनामिक प्रोग्रामिंग का उपयोग करके संख्याओं के योग और उनके अंकों को सरणी arr[18][2][162] में संग्रहीत करेंगे। यहां 18 अधिकतम 18 अंकों की संख्याओं के लिए है, 2 मान 0 और 1 के लिए है। और 162 अधिकतम संभव योग के लिए है यदि सभी 18 अंक 9 हैं ( 18*9=162 )।
तत्व arr[i][j][k] का मान उन संख्याओं की गिनती दर्शाता है जिनके पहले i अंकों पर विचार किया गया है और j 0 या 1 है इस आधार पर कि i अंकों की वर्तमान निर्मित संख्या N में पहले i अंकों की संख्या से कम या ज्यादा है। ( यदि N 123 है और i 2 है तो हम जांचेंगे कि 2 अंकों की संख्याएं 12 के बराबर या अधिक हैं। यदि 12 के बराबर है तो j 1 होगा अन्यथा arr[i][j][k] में j 0 होगा )। इंडेक्स k arr[i][j][k] में i अंकों का योग होगा।
यदि i=N के अंक और k=इनपुट योग तो परिणाम 1 होगा अन्यथा 0।
अगले अंक ( i+1th ) को भरने के लिए हम j की जांच करेंगे। यदि j 1 है तो i-1 अंक N के i-1 अंकों के बराबर हैं इसलिए अगला अंक केवल 0 से N के i+1 th अंक तक के मान रख सकता है ताकि यह <= N बने।
यदि j 0 है तो i-1 अंकों की संख्या N में i-1 अंकों की संख्या से कम है। तो हम अगले अंक ( i+1 th ) स्थिति के लिए 0 से 9 के बीच कोई भी मान रख सकते हैं और यह अभी भी N से कम होगा।
- एक संख्या N दर्शाने वाली स्ट्रिंग str और अंकों के योग के रूप में total लें।
- सरणी arr[18][2][162] लें और memset का उपयोग करके इसे -1 से इनिशियलाइज़ करें।
- फ़ंक्शन count_digits(int i, bool check, int temp, int total, string str, int size) पुनरावर्ती रूप से arr[][][] को भरता है और अंत में दिए गए अंक योग वाली N से छोटी या बराबर संख्याओं की गिनती लौटाता है।
- यदि वर्तमान अंकों की संख्या i N के अंकों के बराबर है और वर्तमान योग temp इनपुट योग total के बराबर है तो 1 लौटाएं अन्यथा 0 लौटाएं।
- count = arr[i][check][temp] लें। यदि यह -1 नहीं है तो परिणाम के रूप में count लौटाएं।
- अस्थायी वेरिएबल check_2 ( bool ) और temp_2 (int ) लें।
- for लूप का उपयोग करके अंकों 0 से 9 को पार करें और तुलना करें कि check 1 या 0 है। यदि 1 है तो वर्तमान अंक ch की तुलना str[i] से करें। यदि यह बड़ा है तो लूप तोड़ें ( कुछ न करें )।
- check_2 = check || ch < str[i] सेट करें।
- temp_2 = temp + (ch - '0') वर्तमान योग के रूप में सेट करें।
- count_digits(i + 1, check_2, temp_2, total, str, size) को 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
