मान लीजिए हमारे पास दो मान n और k हैं। हमें 1 से n की सीमा में लेक्सिकोग्राफिक रूप से kth सबसे छोटा पूर्णांक ज्ञात करना है। इसलिए यदि इनपुट n =14 और k =3 जैसा है, तो आउटपुट 11 होगा, क्योंकि अनुक्रम [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7 होगा। , 8, 9], तो kth संख्या 11 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक फ़ंक्शन को परिभाषित करें findKthNumber(), इसमें n, k, लगेगा
- करा :=1
- (k 1 से घटाएं)
- जबकि k गैर-शून्य है, करें −
- चरण:=फ़ंक्शन को कॉल करें कैल्कस्टेप्स(n, curr, curr + 1)
- यदि चरण <=k, तो −
- k :=k - चरण
- (कर को 1 से बढ़ाएं)
- अन्यथा
- करा :=curr * 10
- k :=k - 1
- वापसी का क्रम
- एक फ़ंक्शन कैल्कस्टेप्स () को परिभाषित करें, इसमें नक्स, n1, n2, लगेगा
- रिट:=0
- जबकि n1 <=nax, करें −
- ret :=ret + न्यूनतम नक्स + 1 और n2 - n1
- n1 :=n1 * 10
- n2 :=n2 * 10
- रिटर्न रिटर्न
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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