Open chadxz opened 3 years ago
First answer was a recursive solution, but javascript does not support tail call recursion so it overflows the stack:
function isPowerOfThree(y) {
return y === 3 || y % 3 === 0 && isPowerOfThree(y / 3);
}
Tail call optimization was added to Node.js v6 behind a flag, but was removed in Node.js v7.
Second answer without recursion:
function isPowerOfThree(y) {
if (y === 3) {
return true;
}
let current = 1;
while (current < y) {
current = current * 3;
}
return current === y;
};
To do it without looping, you'd need to use logarithms
3^x = y ==> log3(y) = x
Math.log() ==> ln() ==> log base e
can use logarithm change of base formula to calculate this based on natural log: log3(y) = ln(y) / ln(3)
Number.isSafeInteger to check if the number is fractional
Math.log() is not precise
Math.round() rounds to the nearest integer
So Math.log(y) / Math.log(3)
should do it, but an example of the precision issue is Math.log(27) / Math.log(3) = 3.0000000000000004
Rounding to 10 decimal places looks like: Math.round(3.9999999999999 * 10000000000) / 10000000000 = 4
Combining these ideas you get: Math.round(Math.log(y) / Math.log(3) * 10000000000) / 10000000000;
Math.round(Math.log(3) / Math.log(3) * 10000000000) / 10000000000 = 1
Math.round(Math.log(9) / Math.log(3) * 10000000000) / 10000000000 = 2
Math.round(Math.log(27) / Math.log(3) * 10000000000) / 10000000000 = 3
Math.round(Math.log(6) / Math.log(3) * 10000000000) / 10000000000 = 1.63093
Full logarithm-based answer:
function isPowerOfThree(y) {
return Number.isSafeInteger(Math.round(Math.log(y) / Math.log(3) * 10000000000) / 10000000000);
};
https://leetcode.com/explore/interview/card/top-interview-questions-easy/102/math/745/