#231
Power of Two
Easy n & (n-1)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether n is a power of two.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: does n have exactly one bit ON?
Why this works: removing the lowest ON bit from a power of two leaves 0.
Example: n = 16 (10000) → 10000 & 01111 = 0 → yes
n = 12 (1100) → 1100 & 1011 = 1000 ≠ 0 → no✦Hints open one at a time
Powers of two have exactly one bit set: 1, 10, 100, 1000 in binary.
What does n & (n - 1) give when only one bit is set?
↗Approach
A positive n is a power of two when clearing its lowest set bit leaves 0.
</>Solution (Java)
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}!Common mistake
Forgetting n > 0. For n = 0, 0 & -1 is 0 and you'd wrongly return true; negatives also break it.
Complexity
- Time: O(1).
- Space: O(1).
