Why is the code failing?
My solution:
class Solution {
public:
class comp{
public:
bool operator() (pair<int,int> a, pair<int,int> b){
if(a.first > b.first){
return true;
}
else if(a.first < b.first){
return false;
}
else{
return a.second>b.second;
}
}
};
int findPow(int num, vector<int> &powerOfX){
cout<<num<<endl;
if(powerOfX[num]!=-1)
return powerOfX[num];
if(num%2==0){
int nextPower = findPow(num/2, powerOfX);
int power = nextPower+1;
powerOfX[num] = power;
return power;
}
else{
int nextPower = findPow(3*num + 1, powerOfX);
int power = nextPower+1;
powerOfX[num] = power;
return power;
}
}
int getKth(int lo, int hi, int k) {
vector<int> powerOfX(200000, -1);
powerOfX[1]=0;
vector<pair<int,int>> res;
for(int i=lo; i<=hi; i++){
int power = findPow(i, powerOfX);
res.push_back({power, i});
cout<<endl;
}
priority_queue<pair<int,int>, vector<pair<int,int>>, comp> pq(res.begin(), res.end());
int ans;
// k=1000;
while(k && pq.size()){
ans = pq.top().second;
cout<<k<<" "<<ans<<" "<<pq.top().first<<endl;
pq.pop();
k--;
}
return ans;
}
};
the code works fine for smaller testcases given in the example, but fails for cases like -
1
1000
777
Please help find the issue…