DEV Community

kevin074
kevin074

Posted on

Leetcode diary: 1387. Sort Integers by The Power Value [DP]

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.

Problem Link

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;
}
Enter fullscreen mode Exit fullscreen mode

Let me know anything on your mind after reading through this, THANKS!

Top comments (0)