যেমন আমরা জানি যে একটি পূর্ণসংখ্যা x এর শক্তিকে নিম্নোক্ত ধাপগুলি ব্যবহার করে x কে 1 এ রূপান্তরিত করার জন্য প্রয়োজনীয় ধাপগুলির সংখ্যা হিসাবে সংজ্ঞায়িত করা হয় -
-
যদি x হয় তাহলে x =x / 2
-
x যদি বিজোড় হয় তাহলে x =3 * x + 1
সুতরাং উদাহরণস্বরূপ, x =3 এর শক্তি 7 কারণ 3 7টি ধাপ ব্যবহার করে 1 হতে পারে (3 → 10 → 5 → 16 → 8 → 4 → 2 → 1)। তাই আমরা কিছু পূর্ণসংখ্যা আছে যদি lo, hi এবং k. আমাদের সমস্ত পূর্ণসংখ্যাকে ব্যবধানে [lo, hi] ক্রমবর্ধমান ক্রমে পাওয়ার মান অনুসারে সাজাতে হবে। এখন যদি দুই বা ততোধিক পূর্ণসংখ্যার শক্তির মান একই থাকে তাহলে তাদের ঊর্ধ্বক্রম অনুসারে সাজান। পাওয়ার মান অনুসারে সাজানো [lo, hi] রেঞ্জে k-th পূর্ণসংখ্যা খুঁজে বের করতে হবে।
উদাহরণস্বরূপ, যদি ইনপুট হয় lo =12, hi =15 এবং k =2, তাহলে আউটপুট 13 হবে। এর কারণ হল 12-এর শক্তি 9, 13-এর শক্তি 9, 14-এর জন্য, এটি 17, এবং 15 এর জন্য এটিও 17, তাই সাজানো ক্রম হল [12,13,14,15] এবং k =2 হিসাবে, তাহলে উপাদানটি 13।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
getTurn পদ্ধতি সংজ্ঞায়িত করুন, এটি n ইনপুট হিসাবে গ্রহণ করবে
-
ret :=0
-
যখন n 1 নয়
-
যদি n বিজোড় হয়, তাহলে n :=n * 3 + 1, অন্যথায় n :=n / 2
-
1 দ্বারা ret বাড়ান
-
-
মূল পদ্ধতি থেকে
-
আমি রেঞ্জের জন্য হাই থেকে হাই
-
একটি জোড়া তৈরি করুন (getTurn(i), i)
-
ret এ temp সন্নিবেশ করান
-
-
শক্তির উপর ভিত্তি করে জোড়া সাজান, অন্যথায় আরোহী ক্রমে
-
পেয়ার ret[k - 1]
এর দ্বিতীয় মান ফেরত দিন
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector < pair <int, int> > ret;
static bool cmp(pair <int, int>& a, pair <int, int>& b){
return a.first == b.first ? a.second < b.second : a.first < b.first;
}
int getTurn(int n){
int ret = 0;
while(n != 1){
if(n & 1){
n = n * 3 + 1;
}
else n >>= 1;
ret ++;
}
return ret;
}
int getKth(int lo, int hi, int k) {
for(int i = lo; i <= hi; i++){
pair <int, int> temp;
temp.first = getTurn(i);
temp.second = i;
ret.push_back(temp);
}
sort(ret.begin(), ret.end(), cmp);
return ret[k - 1].second;
}
};
main(){
Solution ob;
cout << (ob.getKth(12, 15, 2));
} ইনপুট
12 15 2
আউটপুট
13
