231. Power of Two - Explanation

Problem Link

Description

You are 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 == (2^x).

Example 1:

Input: n = 1

Output: true

Explanation: (2^0) is 1.

Example 2:

Input: n = 8

Output: true

Explanation: (2^3) is 8.

Example 3:

Input: n = 12

Output: false

Constraints:

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False

        x = 1
        while x < n:
            x *= 2
        return x == n

Time & Space Complexity

• Time complexity: $O(\log n)$
• Space complexity: $O(1)$

---

2. Recursion

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n == 1:
            return True
        if n <= 0 or n % 2 == 1:
            return False
        return self.isPowerOfTwo(n // 2)

Time & Space Complexity

• Time complexity: $O(\log n)$
• Space complexity: $O(\log n)$ for recursion stack.

---

3. Iteration

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False

        while n % 2 == 0:
            n >>= 1
        return n == 1

Time & Space Complexity

• Time complexity: $O(\log n)$
• Space complexity: $O(1)$

---

4. Bit Manipulation - I

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

Time & Space Complexity

• Time complexity: $O(1)$
• Space complexity: $O(1)$

---

5. Bit Manipulation - II

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

Time & Space Complexity

• Time complexity: $O(1)$
• Space complexity: $O(1)$

---

6. Math

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and ((1 << 30) % n) == 0

Time & Space Complexity

• Time complexity: $O(1)$
• Space complexity: $O(1)$