इस समस्या में, हमें दो मान दिए गए हैं जो योग (अंकों के योग को दर्शाता है) और अंक (अंकों की संख्या को दर्शाता है) हैं। हमारा कार्य दिए गए अंकों की संख्या और अंकों के योग वाली सबसे छोटी संख्या खोजना है।
आइए एक उदाहरण से इस समस्या को समझते हैं,
इनपुट
sum = 15, digit = 2
आउटपुट
69
व्याख्या
योग 15 वाली सभी 2 अंकों की संख्याएं हैं: 69, 78, 87, 96।
समाधान दृष्टिकोण
इस समस्या का एक सरल समाधान उन सभी संख्याओं पर विचार करना है जिनकी अंकों की संख्या अंक के बराबर है और सबसे छोटी संख्या ढूंढना है जिसके अंकों का योग योग के बराबर है।
एक कुशल समाधान लालची दृष्टिकोण का उपयोग करना है। हम अंतिम अंक यानी संख्या के LSB से तत्वों को भरकर संख्या बनाएंगे। हम LSB के लिए सबसे बड़ा संभव तत्व मानेंगे और फिर अगली स्थिति के लिए जाएंगे।
हम LSB को जितना संभव हो उतना बड़ा और MSB को जितना संभव हो उतना छोटा रखने की कोशिश करेंगे।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <iostream> using namespace std; void findSmallestNumWithSum(int digit, int sum) { if (sum == 0) { if(digit == 1) cout<<"Smallest number is 0"; else cout<<"Smallest number with sum cannot be found"; return ; } if (sum > 9*digit) { cout<<"Smallest number with sum cannot be found"; return ; } int number[digit]; sum -= 1; for (int i = digit-1; i>0; i--) { if (sum > 9) { number[i] = 9; sum -= 9; } else { number[i] = sum; sum = 0; } } number[0] = sum + 1; cout<<"Smallest number is "; for (int i=0; i<digit; i++) cout<<number[i]; } int main() { int sum = 15, digit = 3; findSmallestNumWithSum(digit, sum); return 0; }आउटपुट
Smallest number is 159
