#231

Easy

LeetCode Problem Workspace

Power of Two

Determine if a given integer is a power of two using efficient math and bit manipulation techniques with optional recursion support.

math bit manipulation recursion

Problem Statement

Given an integer n, determine whether it is a power of two. Return true if n equals 2 raised to some integer exponent x, otherwise return false. Negative numbers and zero are never powers of two.

For example, when n = 1, the function should return true because 2^0 = 1. If n = 16, return true because 2^4 = 16. If n = 3, return false since no integer x satisfies 2^x = 3. Input constraints are -2^31 <= n <= 2^31 - 1.

Examples

Example 1

Input: n = 1

Output: true

20 = 1

Example 2

Input: n = 16

Output: true

24 = 16

Example 3

Input: n = 3

Output: false

Example details omitted.

Constraints

-231 <= n <= 231 - 1

Solution Approach

Bit Manipulation

Use the property that powers of two have exactly one bit set: n > 0 and n & (n - 1) == 0. This detects the single-bit pattern efficiently in O(1) time without loops.

Recursive Division

Recursively divide n by 2 and check if the result eventually equals 1. If n becomes odd before reaching 1, return false. This leverages the mathematical definition and highlights the pattern of repeated halving.

Mathematical Check with Log

Compute log2(n) and check if it is an integer. This approach ties directly to the exponent x in 2^x = n. It is less efficient than bit manipulation due to floating-point operations but validates the math pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Bit manipulation runs in O(1) time and space. Recursive division can take O(log n) time with O(log n) stack space. Logarithmic checks run in O(1) but may incur floating-point precision overhead.

What Interviewers Usually Probe

Clarifies whether negative numbers and zero should return false.
Hints at using bit manipulation rather than iterative loops.
Tests understanding of the mathematical pattern behind powers of two.

Common Pitfalls or Variants

Common pitfalls

Not handling zero and negative inputs correctly, returning true incorrectly.
Using iterative multiplication or division without stopping conditions, causing infinite loops.
Relying on floating-point logs without tolerance, leading to incorrect results for large n.

Follow-up variants

Check if a number is a power of three or five using a similar recursive or bit-mimicking approach.
Return the largest power of two less than or equal to n using bit manipulation.
Count how many numbers in an array are powers of two using the same n & (n - 1) trick.

FAQ

What is the fastest way to check if a number is a power of two?

The fastest method is using bit manipulation: return n > 0 && (n & (n - 1)) == 0, which checks the single-bit pattern directly.

Can recursion be used to solve Power of Two efficiently?

Yes, recursion divides n by 2 repeatedly until reaching 1, but it uses O(log n) stack space compared to O(1) for bit manipulation.

Why does n & (n - 1) work for detecting powers of two?

Because powers of two have exactly one 1-bit in binary; subtracting 1 flips all lower bits, and ANDing with n clears the single 1-bit if it was a power of two.

Are negative numbers ever considered powers of two?

No, by definition, only positive integers of the form 2^x are powers of two, so negatives always return false.

Does using logarithms provide a reliable solution for large integers?

It works mathematically but may suffer from floating-point precision errors for very large integers, making bit manipulation safer.

terminal

Solution

Solution 1: Bit Manipulation

According to the properties of bit manipulation, executing $\texttt{n\&(n-1)}$ can eliminate the last bit $1$ in the binary form of $n$. Therefore, if $n > 0$ and $\texttt{n\&(n-1)}$ results in $0$, then $n$ is a power of $2$.

1

2

3

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

Solution 2: Lowbit

According to the definition of $\text{lowbit}$, we know that $\text{lowbit}(x) = x \& (-x)$, which can get the decimal number represented by the last bit $1$ of $n$. Therefore, if $n > 0$ and $\text{lowbit}(n)$ equals $n$, then $n$ is a power of $2$.

1

2

3

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

Continue Practicing

#342 power of four #779 k th symbol in grammar #233 number of digit one