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)