Solving The Power of Three Using JavaScript and Logarithms
The Power of Three is a classic beginner programming question. The question goes like this: given a number n, return true if it’s a power of three or false if it’s not. Assume n is greater than 0. Its simple to solve but the most optimal solution is pretty cool as it’s runtime is constant. Constant time solutions are great because they will do a set amount of operations no matter how large the input n is. I will first cover the simple bottom-up solution, then cover logarithms. Next I will explain the constant time solution and how it works. Click on a line below to scroll to the part your most interested in:
Bottom-up Solution
In order to solve on a calculator, you could simply take 3 and multiply it by 3. Keep multiplying that number by 3 until you reach or surpass the input number. If you reach the input number, it’s a power of 3. If you go past the number, it is not. Also any number to the 0th power will be 1. Put into JavaScript the solution looks like this:
const isPowerThree = (n) => {
if(n===1) return true for(let i=3; i<=n; i*=3){ if (i === n) return true } return false}
This solution has a runtime complexity of O(N). This runtime is okay, but it could be better. As with a lot of problems, The Power of Three has a neat constant time solution. It involves using logarithms.
What are logarithms?
Logarithms are the inverse of exponential functions. Here is an example:
Exponential function: 10²=100
Logarithmic function: log(100)=2
The logarithm above has a base of ten. This is the default base on most calculators. The base is the number that is being exponentiated in the exponent function that is the inverse of the logarithm (10 in the exponent example above). If generic logarithm and exponent functions are put on a graph side by side, it’s easy to see how they are inverses of each other:
Solution Using Logarithms
In order to solve this problem using logarithms, we can use a base of 3 instead of 10 (the default base in JavaScript is the number e aka Euler’s number). In order to use a different base in JavaScript, you have to divide the log of the number you want to take the logarithm of by the logarithm of the base. For example, if you want the logarithm of y with a base of x do:
Math.log(y)/Math.log(x)To find the answer take the log base 3 of your given number and if the returned value is a whole number, it’s a power of three.
Sounds simple enough, however if you were to run Math.log(27)/Math.log(3) for example, you would get 3.0000000000000004. This is because of floating point precision errors. You can read more about floating point precision errors here. You only need to be aware of the errors for this problem though. There is a couple ways to get around this issue. One way would be to take the logarithm and convert it to a string. Then cut off the end of the string and convert it back into a float. After that, check if it’s a whole number by seeing if the remainder of modulo 1 is 0. Like so:
const isPowerThree = (n) => {return( parseFloat((Math.log(n)/Math.log(3)).toString().substr(0,15))%1 ===0
)}
Another way to solve using logarithms would be to convert the log back into a number by raising 3 to the logarithm and seeing if it matches the given number n.
const isPowerThree = (n) => {return parseInt(3**parseInt((Math.log(num)/Math.log(3))))===num}
These solutions also can be made to work for any ‘Is Power of X?’ question by just replacing 3 with a function argument like this:
const isPowerOf = (exp,num) => {return parseInt(exp**parseInt((Math.log(num)/Math.log(exp))))===num}
Interestingly, if you were to put these solutions into LeetCode, it would say the bottom-up solution has the best runtime. Perhaps this is due to how Math.log works or parseInt is unexpectedly taxing to run. The logarithm solution converted into Ruby however, when submitted, LeetCode claims the solution is in the top .001% of solution runtime speeds.
def is_power_of_two(n)
return false if n <= 0
2 ** (Math.log(n)/ Math.log(2)).to_i == n
end