> For the complete documentation index, see [llms.txt](https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/week-2/power-of-two.md).

# Power of Two

LeetCode Problem #231 (Easy)

## Problem Statement

Given an integer, write a function to determine if it is a power of two.

## Testcases

```
Example 1:

Input: 1
Output: true 
Explanation: 2^0 = 1

Example 2:

Input: 16
Output: true
Explanation: 2^4 = 16

Example 3:

Input: 218
Output: false
```

## Problem Explanation

A number is a power of two if it can be formed by repeatedly multiplying some number of 2's.

16 is a power of 2 since 16 = 2 \* 2 \* 2 \* 2.

This can alternatively be written as 16 = 2^4.

We must determine whether a particular number is a power of two.

#### Example:

If n = 16

```
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1 and 2 % 2 = 0 -> return true
```

If n = 17

```
17 / 2 = 8
17 % 2 = 1 and n != 1 -> return false
```

## Algorithm

### Iterative Approach

1. If the number is 0, it cannot be a power of 2.
2. If the number is 1, since 2 ^ 0 = 1, it is a power of 2.
3. Iteratively reduce the power of the number by dividing by 2.

   a. If the number % 2 yields a remainder and is not 1, then it is not a power of 2.

   b. If the number evenly divides 2 and yields no remainder, it is a power of 2.

{% hint style="info" %}
Time Complexity: O(logn)
{% endhint %}

## Code

```cpp
bool isPowerOfTwo(int n) {
    // If the number is 0, it cannot be a power of 2
    if(n == 0) {
        return false;
    }
    // If a number does not divide 2 evenly and is not 1 (since, 2 / 2 = 1), then return false
    while(n != 1) {
        if(n % 2 != 0) {
            return false;
        }
        // Iteratively divide the number by 2 to reduce the power
        n /= 2;
    }
    return true;
}
```