Solution
There are not many optimisations which can be done for this question. The only trick is to precompute the powers for 1 to 1000 and store them in a static array. Using a static variable allows us to retain its values across all the tests Leetcode performs so we only have to compute it once for the first test case and then our only job left will be to find the Kth largest value. To answer that, try to solve LC 215. Kth Largest Element in an Array. There are several techniques to solve this question, the below solution uses a min-heap. Another widely used approach is to use nth_element C++ algorithm which employs quick-select algorithm internally (see votrubac’s solution).
// store powers in static vector
static vector<int> powers;
class Solution {
public:
// function to compute power of an integer k as per the rules given
int computePower (int k) {
int count=0;
while (k!=1) {
if (k&1)
k=k*3+1;
else
k/=2;
count++;
}
return count;
}
int getKth(int lo, int hi, int k) {
// precompute the powers for the first test case
if (powers.size()==0) {
for (int i=1; i<=1000; i++) {
powers.push_back(computePower(i));
}
}
// lambda comparator for priority queue
// it compares the integer using powers array
// if power is equal, give higher priority to lower integer
auto comp = [](int a, int b) {
if (powers[a-1]==powers[b-1])
return a<b;
return powers[a-1]<powers[b-1];
};
priority_queue<int, vector<int>, decltype (comp)> pq(comp);
for (int i=lo; i<=hi; i++) {
pq.push(i);
if (pq.size()>k)
pq.pop();
}
return pq.top();
}
};