1387. Sort Integers by The Power Value

The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:

• if x is even then x = x / 2
• if x is odd then x = 3 * x + 1

For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 —> 10 —> 5 —> 16 —> 8 —> 4 —> 2 —> 1).

Given three integers lo, hi and k. The task is to sort all integers in the interval [lo, hi] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.

Return the kth integer in the range [lo, hi] sorted by the power value.

Notice that for any integer x (lo <= x <= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in a 32-bit signed integer.

class Solution {
    unordered_map<int, int> dp;
    int helper(int n) {
        if(dp.count(n)) return dp[n];
        if(n & 1) return dp[n] = 1 + helper(n * 3 + 1);
        return dp[n] = 1 + helper(n / 2);
    }
public:
    int getKth(int lo, int hi, int k) {
        priority_queue<pair<int, int>> q;
        dp[1] = 1;
        for(int i = lo; i <= hi; i++) {
            int p = helper(i);
            q.push({p,i});
            if(q.size() > k) q.pop();
        }
        
        return q.top().second;
    }
};