ধরুন আমাদের দুটি মান আছে n এবং k। আমাদের অভিধানিকভাবে kth ক্ষুদ্রতম পূর্ণসংখ্যাটি 1 থেকে n এর পরিসরে খুঁজে বের করতে হবে। সুতরাং ইনপুট যদি n =14 এবং k =3 এর মত হয়, তাহলে আউটপুট হবে 11, যেমন ক্রম হবে [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7 , 8, 9], তারপর kth সংখ্যা হল 11।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন findKthNumber() সংজ্ঞায়িত করুন, এটি n, k, লাগবে
- curr :=1
- (k 1 দ্বারা কমিয়ে দিন)
- যখন k অ-শূন্য, কর −
- পদক্ষেপ :=ফাংশনটিকে কল করুন calcSteps(n, curr, curr + 1)
- যদি ধাপ <=k হয়, তাহলে −
- k :=k - পদক্ষেপ
- (1 দ্বারা curr বাড়ান)
- অন্যথায়
- curr :=curr * 10
- k :=k - 1
- রিটার্ন কর
- একটি ফাংশন সংজ্ঞায়িত করুন calcSteps(), এটি নেক্স, n1, n2,
- ret :=0
- যখন n1 <=nax, −
- করুন
- ret :=ret + সর্বনিম্ন nax + 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
