Leetcode Daily - August 4, 2020

Power of Four

Link to the Leetcode Question

Lately I've been grinding Leetcode and decided to record some of my thoughts on this blog. This is both to help me look back on what I've worked on as well as help others see how one might think about the problems.

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted from Leetcode)

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

Input: 16
Output: true

Example 2:

Input: 5
Output: false

Follow up: Could you solve it without loops/recursion?

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - while loop

(Did not submit, only pseudocoded)

I believe most people understand how to iteratively solve this problem. The two possible ways to use the iterative method are:

• Via multiplication

function isPowerOfFour(num) {
 let counter = 1 
 while (counter < num) {
   counter *= 4
   if (counter === num) return true 
 }
 return false 
}

• Via division

function isPowerOfFour(num) {
 let counter = num
 while (counter > 1) {
   counter /= 4
   if (counter === 1) return true 
 }
 return false 
}

These methods are O(log(n)) because the number of iterations would basically be the power of 4 that the number is closest to.

Attempt 2 - Math.log

(Submission - Accepted)

For those that are not familiar with the logarithm mathematical function, please refer to my post about it, here.

Basically, if 4^N = num, then log₄(num) = N.

We can also use the mathematical theorem that converts logarithms to a common basis:

• log_B(A) = log_x(A) / log_x(B)

where x is a common basis. We will simply use base 10 since most log functions are base 10.

By understanding that powers of 4 will only have log₄(num) = N where N are whole numbers, we can write a very simple function:

function isPowerOfFour(num) {
    return Math.log(num)/Math.log(4) % 1 === 0
};

After submitting this solution I noticed the run time was a bit long, 140ms. I think it might be that Math.log uses an iterative method to calculate the log accurately but that's required for this solution so the method I found (discussed in the Conclusions Section could be a more computationally efficient alternative.

Discussion and Conclusions

I felt very satisfied with solution, but looked for other interesting solutions. Here is one that uses some programming knowledge as well as mathematical knowledge.

First of all, since the question is asking about a power of 4, which is a power of 2, it has a significant property in binary, which is that it is a one with all zeros to the right of it. Not only that, it must be an even number of zeros since the odd powers of 2, such as 8 = 2³, would have an odd number of zeros (3 zeros for the number 8).

This solution also takes advantage of the fact that the programmer can know the maximum size of the number in bits, which allows them to use a bit mask and therefore not have to write iteration in a higher level language.