Power of two
Problem Link
Problem Statement
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 == 2ˣ
Examples
Example 1:
Input: n = 1
Output: true
Explanation: 2⁰ = 1
Example 2:
Input: n = 16
Output: true
Explanation: 2⁴ = 16
Example 3:
Input: n = 3
Output: false
Explanation: No power of 2 gives 3
Constraints
-2³¹ <= n <= 2³¹ - 1
Intuition
A number is a power of two if and only if it has exactly one 1 bit in its binary representation.
Examples:
-
1=0001→ power of 2 -
2=0010→ power of 2 -
3=0011→ not a power of 2 -
4=0100→ power of 2
This means: if we remove the only set bit, the result should be 0.
Key property:
n & (n - 1) == 0 ⇨ n is a power of 2
Only true when n has exactly one bit set.
Approach: Bit Manipulation
-
First, check if
nis positive (since powers of two are positive). -
Use the identity:
n & (n - 1) == 0-
This removes the lowest set bit.
-
If only one bit was set (i.e., power of two), result becomes
0.
-
Java Code
class Solution {
public boolean isPowerOfTwo(int n) {
if(n <= 0) return false;
return (n & (n - 1)) == 0;
}
}
Time and Space Complexity
| Metric | Value |
|---|---|
| Time Complexity | O(1) |
| Space Complexity | O(1) |
| Explanation | Uses constant-time bitwise operations |
Dry Run
Input: n = 16
-
Binary of
n:10000 -
n - 1:01111 -
n & (n - 1)=10000 & 01111=00000→0→ power of two → returnstrue
Input: n = 18
-
Binary of
n:10010 -
n - 1:10001 -
n & (n - 1)=10010 & 10001=10000≠0→ not a power of two → returnsfalse
Conclusion
This problem highlights one of the most elegant and efficient uses of bit manipulation:
-
Avoids loops and recursion
-
Works in constant time
-
Leverages the mathematical property of binary representations