How do you solve Power of Two on LeetCode?

Power of Two (LeetCode #231) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(1) space complexity. Key insight: A power of two has exactly one bit set in its binary representation.

What is the brute force solution for Power of Two?

The brute force approach for Power of Two is Brute Force, with O(log n) time complexity and O(1) space complexity. To determine if a number is a power of two, we can repeatedly divide the number by 2 until we reach 1. If at any point the number becomes odd before reaching 1, it is not a power of two. The optimal Optimal Solution approach improves this to O(1).

What algorithm or data structure is used to solve Power of Two?

Power of Two uses the following concepts: Math, Bit Manipulation, Recursion. The recommended patterns to study are: Bit Manipulation, Mathematical Properties.

What are the interview tips for Power of Two?

Always consider edge cases like negative numbers and zero. Explain your thought process clearly while coding. If you can optimize with bit manipulation, mention it as a potential solution.

What are common mistakes when solving Power of Two?

Not checking for negative numbers or zero, which cannot be powers of two. Confusing the condition for powers of two with other conditions.

#231

Power of Two

Easy

MathBit ManipulationRecursionBit ManipulationMathematical Properties

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(log n)	O(1)
Space	O(1)	O(1)

💡

Intuition

Time O(1)Space O(1)

A more efficient way to check if a number is a power of two is to use bit manipulation. A power of two has exactly one bit set in its binary representation.

⚙️

Algorithm

2 steps

1Step 1: If n is less than or equal to 0, return false.
2Step 2: Check if n & (n - 1) equals 0. This checks if there is only one bit set in n.

solution.py4 lines

1# Full working Python code
2
3def isPowerOfTwo(n):
4    return n > 0 and (n & (n - 1)) == 0

ℹ

Complexity note: The time complexity is O(1) because we are performing a constant-time bitwise operation. The space complexity is O(1) as well since we are using a constant amount of space.

1A power of two has exactly one bit set in its binary representation.
2Using bit manipulation can significantly reduce the time complexity.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.