# 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**