# Power of Two
**Difficulty:** EASY
[External](https://leetcode.com/problems/power-of-two)
Canonical: https://scaleengineer.com/dsa/problems/power-of-two
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Companies:** [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Wipro](https://scaleengineer.com/companies/wipro), [tcs](https://scaleengineer.com/companies/tcs), [Snap](https://scaleengineer.com/companies/snap)
---
## Problem
Given an integer `n`, return _`true` if it is a power of two. Otherwise, return `false`_.

An integer `n` is a power of two, if there exists an integer `x` such that `n == 2x`.

**Example 1:**

**Input:** n = 1
**Output:** true
**Explanation:** 20 = 1

**Example 2:**

**Input:** n = 16
**Output:** true
**Explanation:** 24 = 16

**Example 3:**

**Input:** n = 3
**Output:** false

**Constraints:**

* `-231 <= n <= 231 - 1`

**Follow up:** Could you solve it without loops/recursion?

# Approaches
## Iterative Division Approach
Check if a number is a power of two by repeatedly dividing by 2 until we either reach 1 (power of two) or get an odd number (not a power of two).
**Time:** O(log n) - we divide the number by 2 in each iteration · **Space:** O(1) - only uses a constant amount of space
**Pros:** Simple to understand and implement; Works well for small numbers; Straightforward logic
**Cons:** Not the most efficient solution; Uses a loop; Number of iterations depends on the input size
### Explanation
This approach works by continuously dividing the number by 2 and checking if at any point we get an odd number before reaching 1. If we reach 1, it means the number was a power of 2. If we get an odd number before reaching 1, it's not a power of 2.

```java
public boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;
    
    while (n > 1) {
        if (n % 2 != 0) return false;
        n = n / 2;
    }
    return true;
}
```

First, we check if n is less than or equal to 0, as negative numbers and zero cannot be powers of 2. Then, we keep dividing n by 2 until either we find an odd number (return false) or reach 1 (return true).
### Algorithm
1. Check if n ≤ 0, return false if true
2. While n > 1:
   - If n is odd (n % 2 != 0), return false
   - Divide n by 2
3. Return true

## Bit Count Approach
Count the number of set bits (1s) in the binary representation of the number. A number is a power of two if and only if it has exactly one set bit.
**Time:** O(1) - bitCount is a constant time operation in Java · **Space:** O(1) - only uses a constant amount of space
**Pros:** More efficient than iterative division; Clean and concise code; Uses built-in function
**Cons:** Relies on built-in function; May not be available in all programming languages; Implementation of bitCount itself might be complex
### Explanation
This approach uses Java's built-in Integer.bitCount() method to count the number of 1s in the binary representation. A number is a power of two if and only if it has exactly one bit set to 1.

```java
public boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return Integer.bitCount(n) == 1;
}
```

For example:
- 16 (10000) has one 1, so it's a power of 2
- 12 (1100) has two 1s, so it's not a power of 2
### Algorithm
1. Check if n ≤ 0, return false if true
2. Count the number of set bits in n
3. Return true if the count is exactly 1

## Bit Manipulation Approach
Use the property that powers of 2 have exactly one bit set in their binary representation, and when we subtract 1 from a power of 2, all bits to the right of that bit become 1.
**Time:** O(1) - single bit operation · **Space:** O(1) - only uses a constant amount of space
**Pros:** Most efficient solution; No loops or recursion; Constant time operation; Very concise code
**Cons:** Requires understanding of bit manipulation; Less intuitive than other approaches; Need to handle negative numbers separately
### Explanation
This approach uses a clever bit manipulation trick. For a power of 2, n & (n-1) will always be 0. This is because a power of 2 has only one bit set, and subtracting 1 from it will set all bits to the right of that bit to 1 and that bit to 0.

```java
public boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}
```

For example:
- For n = 8 (1000), n-1 = 7 (0111)
- 1000 & 0111 = 0000
- Therefore 8 is a power of 2
### Algorithm
1. Check if n ≤ 0, return false if true
2. Return true if n & (n-1) equals 0

# Solutions
### Java

```java
class Solution { public boolean isPowerOfTwo ( int n ) { return n > 0 && ( n & ( n - 1 )) == 0 ; } }
```

### JavaScript

```javascript
/** * @param {number} n * @return {boolean} */ var isPowerOfTwo = function (n) {
  return n > 0 && (n & (n - 1)) == 0;
};

```

### CPP

```cpp
class Solution { public: bool isPowerOfTwo ( int n ) { return n > 0 && ( n & ( n - 1 )) == 0 ; } };
```

### Python

```python
class Solution : def isPowerOfTwo ( self , n : int ) -> bool : return n > 0 and ( n & ( n - 1 )) == 0
```