LeetCode #231 — Power of Two

Find more useful articles at www.davidseek.com

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 n?

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.

1) 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 ( 2^1 ).

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 Int.max

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 O(n) where 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.

Find more useful articles at www.davidseek.com

Software Engineer at Amazon (Alexa Mobile)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store