This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.
This problem is rather easy, a good out-out-entry-level DP problem.
My thought process is this:
1.) getPower() is easy to understand: I just run a while loop to decrease the number via the rule listed by the problem.
2.) we now memoize. This can be achieved simply by remembering how many steps is necessary for a particular number. We can return this memoized number whenever the while loop reaches this number. 
3.) we create the [lo ... high] then just sort based on the their power number and return the k-1th element by the sort (honestly though, why didn't the stupid problem just give k-1th number instead of k?).
Below is the code:
var getKth = function(lo, hi, k) {
    let nums = [];
    for (let i=lo; i<=hi; i++) {
        nums.push(i);
    };
    nums.sort(function(a,b){
        const powerA = getPower(a);
        const powerB = getPower(b);
        if(powerA === powerB) return a > b ? 1 : -1;
        return powerA > powerB ? 1 : -1;
    });
    return nums[k-1];
};
const memo = {}
function getPower (number) {
    const numberHolder = number;
    let step = 0;
    while (number >1) {
        if (memo.hasOwnProperty(number)) {
            step += memo[number];
            break;
        }
        if(number % 2 === 0) {
            number = number /2 
        }
        else {
            number = number * 3 + 1
        }
        step++;
    }
    memo[numberHolder] = step;
    return step;
}
Let me know anything on your mind after reading through this, THANKS!
    
Top comments (0)