जैसा कि हम जानते हैं कि एक इंटीजर x की पावर को उन स्टेप्स की संख्या के रूप में परिभाषित किया गया है जिनकी आवश्यकता x को 1 में बदलने के लिए निम्न स्टेप्स का उपयोग करके होती है:
अगर x सम है तो x = x / 2
अगर x विषम है तो x = 3 * x + 1
उदाहरण के लिए, x = 3 की पावर 7 है क्योंकि 3 को 1 बनने में 7 स्टेप्स लगते हैं (3 → 10 → 5 → 16 → 8 → 4 → 2 → 1)। तो अगर हमारे पास कुछ इंटीजर्स lo, hi और k हैं। हमें अंतराल [lo, hi] में सभी इंटीजर्स को पावर वैल्यू के आरोही क्रम में सॉर्ट करना है। अब अगर दो या अधिक इंटीजर्स की पावर वैल्यू समान है तो उन्हें आरोही क्रम में सॉर्ट करें। हमें पावर वैल्यू द्वारा सॉर्ट की गई रेंज [lo, hi] में k-वां इंटीजर ढूंढना है।
उदाहरण के लिए, अगर इनपुट 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
ret को 1 से बढ़ाएं
मेन मेथड से:
i को lo से hi तक लूप करें:
(getTurn(i), i) का एक पेयर बनाएं
temp को ret में इंसर्ट करें
पेयर्स को पावर के आधार पर सॉर्ट करें, अन्यथा आरोही क्रम में
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;
}
};
int main(){
Solution ob;
cout << (ob.getKth(12, 15, 2));
}
इनपुट
12 15 2
आउटपुट
13
