Domain 1EasyCORE

Power of Two

The problem asks us to determine if a given integer `n` is a power of two. In other words, we need to check if there exists an integer `x` such that `n == 2^x`. The input is a single integer `n`, and the output should be a boolean value: `true` if `n` is a power of two, and `false` otherwise.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math#Bit Manipulation

231. Power of Two

Model: qwen2.5-coder:14b
Topics: Math,Bit Manipulation
FAANG asked: 1
Acceptance rate: 43.8%


Problem Breakdown

The problem asks us to determine if a given integer n is a power of two. In other words, we need to check if there exists an integer x such that n == 2^x. The input is a single integer n, and the output should be a boolean value: true if n is a power of two, and false otherwise.

Inputs: An integer n.

Outputs: A boolean value (true or false).

Implicit Constraints/Edge Cases:

  • If n is less than 1, it cannot be a power of two.
  • The function should handle the full range of 32-bit signed integers, from -2^31 to 2^31 - 1.
  • Special cases include n = 0, which is not a power of two.

Intuition

A brute-force approach would involve iterating through powers of two starting from 2^0 and checking if any of them equal n. However, this approach is inefficient because it involves looping until we exceed the value of n, leading to a time complexity of O(log n).

The key insight for an efficient solution is to use bit manipulation. Powers of two in binary representation have exactly one bit set (e.g., 1 = 0001, 2 = 0010, 4 = 0100). Therefore, if we subtract 1 from a power of two, all the bits after the rightmost set bit will flip. For example, 8 - 1 = 7 in binary is 1000 - 0001 = 0111. Thus, n & (n - 1) will be zero if n is a power of two.

Approach

We will use bit manipulation to determine if n is a power of two. The steps are as follows:

  1. Check if n is greater than 0 because negative numbers and zero cannot be powers of two.
  2. Use the bitwise AND operation between n and n - 1. If the result is 0, then n is a power of two; otherwise, it is not.

Complexity Analysis

  • Time Complexity: O(1) because the operations are constant time bit manipulations.
  • Space Complexity: O(1) as no additional space is used beyond a few variables.

Solution

def isPowerOfTwo(n: int) -> bool:
    # Check if n is greater than 0 and if n & (n - 1) is 0
    return n > 0 and (n & (n - 1)) == 0

Edge Cases Handled

  • Negative Numbers: The condition n > 0 ensures that negative numbers are immediately returned as false.
  • Zero: The condition n > 0 also handles the case where n is zero, returning false since zero is not a power of two.
  • Maximum and Minimum Values: The bitwise operation works correctly within the range of 32-bit signed integers.