Power of Two
EasyPrompt
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.
Example 1:
Input: n = 1
Output: true
Explanation: 20 = 1Example 2:
Input: n = 16
Output: true
Explanation: 24 = 16Example 3:
Input: n = 3
Output: false
Constraints:
-231 <= n <= 231 - 1
Follow up: Could you solve it without loops/recursion?
Approaches
3 approaches with complexity analysis and trade-offs.
Check if a number is a power of two by repeatedly dividing by 2 until we either reach 1 (power of two) or get an odd number (not a power of two).
Algorithm
- Check if n ≤ 0, return false if true
- While n > 1:
- If n is odd (n % 2 != 0), return false
- Divide n by 2
- Return true
Walkthrough
This approach works by continuously dividing the number by 2 and checking if at any point we get an odd number before reaching 1. If we reach 1, it means the number was a power of 2. If we get an odd number before reaching 1, it's not a power of 2.
public boolean isPowerOfTwo(int n) { if (n <= 0) return false; while (n > 1) { if (n % 2 != 0) return false; n = n / 2; } return true;}First, we check if n is less than or equal to 0, as negative numbers and zero cannot be powers of 2. Then, we keep dividing n by 2 until either we find an odd number (return false) or reach 1 (return true).
Complexity
Time
O(log n) - we divide the number by 2 in each iteration
Space
O(1) - only uses a constant amount of space
Trade-offs
Pros
Simple to understand and implement
Works well for small numbers
Straightforward logic
Cons
Not the most efficient solution
Uses a loop
Number of iterations depends on the input size
Solutions
Solution
class Solution { public boolean isPowerOfTwo ( int n ) { return n > 0 && ( n & ( n - 1 )) == 0 ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.