मान लीजिए हमारे पास दो मान n और k हैं। हमें 1 से n की सीमा में शब्दकोश क्रम में kवां सबसे छोटा पूर्णांक ढूंढना है। तो यदि इनपुट n = 14 और k = 3 जैसा है, तो आउटपुट 11 होगा, क्योंकि अनुक्रम [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7, 8, 9] होगा, फिर kवीं संख्या 11 है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- एक फ़ंक्शन findKthNumber() परिभाषित करें, जो n, k लेगा,
- curr := 1
- (k को 1 से घटाएं)
- जब k शून्येतर है, करें -
- steps := फ़ंक्शन calcSteps(n, curr, curr + 1) को कॉल करें
- यदि steps <= k, तो -
- k := k - steps
- (curr को 1 से बढ़ाएं)
- अन्यथा
- curr := curr * 10
- k := k - 1
- curr लौटाएं
- एक फ़ंक्शन calcSteps() परिभाषित करें, जो nax, n1, n2 लेगा,
- ret := 0
- जब n1 <= nax, करें -
- ret := ret + nax + 1 और n2 - n1 का न्यूनतम
- n1 := n1 * 10
- n2 := n2 * 10
- ret लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: int findKthNumber(int n, int k) { int curr = 1; k--; while(k){ int steps = calcSteps(n, curr, curr + 1); if(steps <= k){ k -= steps; curr++; }else{ curr *= 10; k -= 1; } } return curr; } int calcSteps(lli nax, lli n1, lli n2){ int ret = 0; while(n1 <= nax){ ret += min(nax + 1, n2) - n1; n1 *= 10; n2 *= 10; } return ret; } }; main(){ Solution ob; cout << (ob.findKthNumber(14,3)); }इनपुट
14,3
आउटपुट
11
