লেক্সিকোগ্রাফিকাল অর্ডার সমস্যা
দুটি মান n এবং k দেওয়া আছে। ১ থেকে n পর্যন্ত의 সকল পূর্ণসংখ্যাকে লেক্সিকোগ্রাফিকাল (শব্দকোষিক) ক্রমে সাজালে k-তম সংখ্যাটি কত?
উদাহরণ: n = 14, k = 3 হলে ক্রম হবে: [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7, 8, 9]। তাই ৩য় সংখ্যা হলো 11।
সমাধানের পদ্ধতি (প্রিফিক্স ট্রি / ট্রাই ওপ্টিমাইজেশন)
সभी সংখ্যা একটি ১০-শাখা ট্রাই-তে ভিজ্যুアライজ করা যায়। আমরা প্রিফিক্স ভিত্তিক স্টেপ গণনা করে k-তম উপাদান খুঁজে বের করি।
findKthNumber(n, k):curr := 1,k--while k > 0:steps := calcSteps(n, curr, curr + 1)- যদি
steps ≤ k:k -= steps; curr++(বর্তমান প্রিফিক্স স্কিপ করুন) - অন্যথায়:
curr *= 10; k--(গভীরে যান)
currফেরত দিন
calcSteps(n, n1, n2): প্রিফিক্সn1এবংn2এর মধ্যেn-এর অধীনে কত সংখ্যা আছে তা গণনা করুন
C++ কোড উদাহরণ
#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;
}
};
int main() {
Solution ob;
cout << (ob.findKthNumber(14, 3));
return 0;
}
ইনপুট
14,3
আউটপুট
11
