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
nis less than 1, it cannot be a power of two. - The function should handle the full range of 32-bit signed integers, from
-2^31to2^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:
- Check if
nis greater than 0 because negative numbers and zero cannot be powers of two. - Use the bitwise AND operation between
nandn - 1. If the result is 0, thennis 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 > 0ensures that negative numbers are immediately returned asfalse. - Zero: The condition
n > 0also handles the case wherenis zero, returningfalsesince zero is not a power of two. - Maximum and Minimum Values: The bitwise operation works correctly within the range of 32-bit signed integers.