Power of Two

Difficulty: Easy | Acceptance: 50.10% | Paid: No Topics: Math, Bit Manipulation, Recursion

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.

• Examples
• Constraints
• Approach 1: Iterative Division
• Approach 2: Bit Manipulation (n & (n-1))
• Approach 3: Bit Manipulation (n & -n)
• Approach 4: Math & Logarithms
• Approach 5: Recursion

Examples

Input: n = 1
Output: true
Explanation: 2⁰ = 1

Input: n = 16
Output: true
Explanation: 2⁴ = 16

Input: n = 3
Output: false

Constraints

-2³¹ <= n <= 2³¹ - 1

Approach 1: Iterative Division

Intuition If a number is a power of two, we can continuously divide it by 2. If we eventually reach 1, it is a power of two. If we encounter an odd number greater than 1, it is not.

Steps

• Check if n is less than or equal to 0. If so, return false.
• Use a while loop to iterate while n is even (n % 2 == 0).
• Inside the loop, divide n by 2.
• After the loop, check if n is equal to 1.

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

Complexity

• Time: O(log n)
• Space: O(1)
• Notes: Simple logic, but slower than bit manipulation.

Approach 2: Bit Manipulation (n & (n-1))

Intuition A power of two in binary representation has exactly one bit set to 1 (e.g., 8 is 1000). If we subtract 1 from a power of two, all bits to the right of that set bit flip to 1, and the set bit becomes 0 (e.g., 7 is 0111). The bitwise AND of these two numbers is always 0.

Steps

• Check if n is greater than 0.
• Return the result of (n & (n - 1)) == 0.

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

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Highly efficient, commonly used bit trick.

Approach 3: Bit Manipulation (n & -n)

Intuition In two’s complement representation, -n is equivalent to ~n + 1. The operation n & -n isolates the lowest set bit of n. For a power of two, there is only one set bit, so n & -n equals n.

Steps

• Check if n is greater than 0.
• Return the result of n == (n & -n).

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

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Efficient, relies on two’s complement arithmetic.

Approach 4: Math & Logarithms

Intuition If n is a power of two, then log₂(n) is an integer. We can calculate the logarithm and check if it is a whole number.

Steps

• Check if n is greater than 0.
• Calculate the base-2 logarithm of n.
• Check if the result is an integer (modulo 1 equals 0).

import math

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

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Susceptible to floating-point precision errors for very large integers.

Approach 5: Recursion

Intuition We can recursively divide n by 2. The base cases are n == 1 (true) and n <= 0 or n is odd (false).

Steps

• If n <= 0, return false.
• If n == 1, return true.
• If n is odd (n % 2 != 0), return false.
• Otherwise, return the result of isPowerOfTwo(n / 2).

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

Complexity

• Time: O(log n)
• Space: O(log n)
• Notes: Uses stack space proportional to the number of divisions.