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.