वे संख्याएं जिनके अंकों का योग 10 के बराबर है:
19, 28, 37, 46, 55, 64, 73, 82, 91, आदि।
यदि आप श्रृंखला का निरीक्षण करते हैं, तो प्रत्येक संख्या 9 से बढ़ाई जाती है। उपरोक्त क्रम में ऐसी संख्याएं हैं जिनके अंकों का योग 9 से बढ़ाने पर 10 के बराबर नहीं होता है। लेकिन, आपको वे सभी संख्याएं मिल जाएंगी जिनके अंकों का योग 10 के बराबर है।
तो, हम एक लूप रख सकते हैं जो 9 से बढ़ता है और अंकों के योग की जांच करता है और nवीं संख्या ढूंढता है। आइए कुछ उदाहरण देखें:
इनपुट्स
3 7
आउटपुट्स
37 73
एल्गोरिथ्म
- संख्या n इनिशियलाइज़ करें
- एक काउंटर को 0 पर इनिशियलाइज़ करें।
- एक लूप लिखें जो 19 से पुनरावृति करता है
- यदि वर्तमान संख्या का अंकों का योग 10 है, तो काउंटर को 1 से बढ़ाएं।
- यदि काउंटर n के बराबर है, तो वर्तमान संख्या लौटाएं।
- पुनरावृत्ति वेरिएबल को 9 से बढ़ाएं।
कार्यान्वयन
उपरोक्त एल्गोरिथ्म का C++ में कार्यान्वयन निम्नलिखित है:
#include <bits/stdc++.h>
using namespace std;
int findNthNumber(int n) {
int count = 0, i = 19;
while (true) {
int sum = 0;
for (int number = i; number > 0; number = number / 10) {
sum = sum + number % 10;
}
if (sum == 10) {
count++;
}
if (count == n) {
return i;
}
i += 9;
}
return -1;
}
int main() {
int n = 7;
cout << findNthNumber(7) << endl;
return 0;
}
आउटपुट
यदि आप उपरोक्त कोड चलाते हैं, तो आपको निम्नलिखित परिणाम मिलेगा।
73
समय जटिलता विश्लेषण
- समय जटिलता: O(n * log(max_number)) - जहां max_number लगभग 19 + 9*n है
- स्पेस जटिलता: O(1)
- यह दृष्टिकोण काम करता है क्योंकि वैध संख्याओं के बीच का अंतर 9 का गुणक होता है
अनुकूलन नोट
बड़े n के लिए, डिजिट DP या गणितीय सूत्र का उपयोग करके O(log n) में गणना की जा सकती है।
