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.

```
func isPowerOfTwo(_ n: Int) -> Bool {
// 1
guard n != 1 && n != 2 else {
return true
}
// 2
var last: Int = 2
// 3
for index in 2...Int.max {
// 4
let current = last * 2
// 5
if current == n {
return true
}
// 6
if current > n {
return false
}
// 7
last = current
}
// 8
return false
}
```

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