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
Count the number of set bits (1s) in the binary representation of the number. A number is a power of two if and only if it has exactly one set bit.
Algorithm
- Check if n ≤ 0, return false if true
- Count the number of set bits in n
- Return true if the count is exactly 1
Walkthrough
This approach uses Java's built-in Integer.bitCount() method to count the number of 1s in the binary representation. A number is a power of two if and only if it has exactly one bit set to 1.
public boolean isPowerOfTwo(int n) { if (n <= 0) return false; return Integer.bitCount(n) == 1;}For example:
- 16 (10000) has one 1, so it's a power of 2
- 12 (1100) has two 1s, so it's not a power of 2
Complexity
Time
O(1) - bitCount is a constant time operation in Java
Space
O(1) - only uses a constant amount of space
Trade-offs
Pros
More efficient than iterative division
Clean and concise code
Uses built-in function
Cons
Relies on built-in function
May not be available in all programming languages
Implementation of bitCount itself might be complex
Use the property that powers of 2 have exactly one bit set in their binary representation, and when we subtract 1 from a power of 2, all bits to the right of that bit become 1.
Algorithm
- Check if n ≤ 0, return false if true
- Return true if n & (n-1) equals 0
Walkthrough
This approach uses a clever bit manipulation trick. For a power of 2, n & (n-1) will always be 0. This is because a power of 2 has only one bit set, and subtracting 1 from it will set all bits to the right of that bit to 1 and that bit to 0.
public boolean isPowerOfTwo(int n) { if (n <= 0) return false; return (n & (n - 1)) == 0;}For example:
- For n = 8 (1000), n-1 = 7 (0111)
- 1000 & 0111 = 0000
- Therefore 8 is a power of 2
Complexity
Time
O(1) - single bit operation
Space
O(1) - only uses a constant amount of space
Trade-offs
Pros
Most efficient solution
No loops or recursion
Constant time operation
Very concise code
Cons
Requires understanding of bit manipulation
Less intuitive than other approaches
Need to handle negative numbers separately
Solutions
Solution
class Solution { public boolean isPowerOfTwo ( int n ) { return n > 0 && ( n & ( n - 1 )) == 0 ; } }/** * @param {number} n * @return {boolean} */ var isPowerOfTwo = function (n) { return n > 0 && (n & (n - 1)) == 0;};class Solution { public: bool isPowerOfTwo ( int n ) { return n > 0 && ( n & ( n - 1 )) == 0 ; } };class Solution : def isPowerOfTwo ( self , n : int ) -> bool : return n > 0 and ( n & ( n - 1 )) == 0Video 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.