इस समस्या में, हमें दो पूर्णांक मान दिए गए हैं, N जो संख्या के अंकों की संख्या को दर्शाता है और sum जो संख्या के अंकों के योग को दर्शाता है। हमारा कार्य दिए गए अंकों की संख्या और अंकों के योग के साथ सबसे बड़ी संख्या ज्ञात करना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट : N = 3, sum = 15 आउटपुट : 960
समाधान दृष्टिकोण
समस्या को हल करने का एक सरल दृष्टिकोण सभी N अंकों की संख्याओं को सबसे बड़ी से सबसे छोटी तक पार करना है। अंकों का योग ढूंढें, यदि यह sum के बराबर है तो संख्या लौटाएं।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <iostream> using namespace std; int digitSum(int n){ int sum = 0; while(n){ sum += n%10; n = n/10; } return sum; } int findLargestNumWithSum(int N, int sum){ if (sum == 0){ if(N == 1) return -1; else return -1; } if (sum > 9*N){ return -1; } int num = 1; for(int i = 0; i < N; i++) num *= 10; while(1){ if(digitSum(num) == sum){ return num; } num -- ; if(num == 0) return -1; } } int main(){ int sum = 25, N = 3; cout<<"सबसे बड़ी "<<N<<" अंकों की संख्या जिसका योग "<<sum<<" है "<< findLargestNumWithSum(N, sum); return 0; } आउटपुट
सबसे बड़ी 3 अंकों की संख्या जिसका योग 25 है 997
समस्या को हल करने का एक अन्य दृष्टिकोण लालची दृष्टिकोण का उपयोग करना है। हम इसे MSB से शुरू करके, sum से उच्चतम संभव संख्या रखकर और इसे sum से घटाकर करेंगे।
हम इस चरण को N बार करेंगे, हमें आवश्यक संख्या मिल जाएगी। तो, यदि sum 9 से अधिक है, तो वर्तमान अंक पर 9 रखें, यदि यह 9 से कम है, तो वर्तमान अंक पर sum रखें। इस प्रक्रिया को MSB से LSB तक सभी अंकों के लिए करें।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <iostream> using namespace std; int findLargestNumWithSum(int N, int sum){ if (sum == 0){ if(N == 1) return -1; else return -1; } if (sum > 9*N){ return -1; } int num = 0; for (int i = 0; i < N; i++){ if (sum >= 9){ num += 9; sum -= 9; if(i < (N - 1)){ num *= 10; } } else{ num += sum; sum = 0; if( i < (N - 1)) num *= 10; } } return num; } int main(){ int sum = 25, N = 3; cout<<"सबसे बड़ी "<<N<<" अंकों की संख्या जिसका योग "<<sum<<" है "<<findLargestNumWithSum(N, sum); return 0; } आउटपुट
सबसे बड़ी 3 अंकों की संख्या जिसका योग 25 है 997