LeetCode's challenge of the day on June 8, 2020 (#231) asks us to write a function that determines if the given Integer
n is a power of two. In other words: If we multiply the number 2 any amount of times, will we end up with
This is a typical dynamic programming problem. We could solve it with recursion. Using a helper function, we would pass
n and the
current multiplication. But, if
n is large enough, the function would be called thousands of times and we might run into
stack overflow protection and get a
Segment 11 error code.
Bottom Up Approach
The approach we will use is called the Bottom Up Approach. The idea is that we are utilizing a
dp array. "dp" stands for dynamic programming and naming the array
dp is a convention widely used in tech challenges and interviews.
2^0 is explained in the examples as
n = 1 and
2^1 is logically
2. Those are our exit conditions.
2) Based on the exit condition in 1), 2 is the last value we have processed (
3) Since we don't know how many multiples we will need to end up at
n, we're using a for loop from 2 up to
4) First, within the loop we will get the last processed number and multiply it by 2 to get the current number.
5) Then, we are checking if
current equals the given number
n. If so, return true.
6) If the current number is larger than
n, we know that
n is not a power of two and we need to return false.
7) Update the last element using the current one and continue the loop.
8) Lastly, we return false to satisfy the compiler.
Time and space complexity
The time complexity is expressed as
n is the possible multiples between
0 and the given integer
n. The space complexity is linear as we're only storing the last processed variable.