Power of Two
Power of Two is a easy bit manipulation problem solved with the tricks to remember pattern.
The best approach, optimal (clear the lowest set bit), runs in O(1) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (keep dividing by 2) up.
Problem
Given an integer n, return true if it equals 2^k for some integer k >= 0, and false otherwise.
Note that 1 is a power of two (2^0), while zero and negative numbers never are.
Examples
Example 1
- Input
n = 64- Output
true- Why
- 64 = 2^6.
Example 2
- Input
n = 24- Output
false- Why
- 24 = 2^3 · 3, and the factor 3 means it is not a power of two.
Example 3
- Input
n = 1- Output
true- Why
- 1 = 2^0 counts as a power of two.
Constraints
-2^31 <= n <= 2^31 - 1
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (keep dividing by 2) | O(log n) | O(1) |
| Optimal (clear the lowest set bit) | O(1) | O(1) |
1Brute force (keep dividing by 2)
O(log n)Each step halves n, so there are at most 31 steps for a 32-bit int.O(1)Only the number itself is updated.A positive number is a power of two exactly when dividing it by 2 repeatedly never leaves a remainder and ends at 1. Zero and negatives are rejected up front.
- If n <= 0, return false.
- While n is even, divide it by 2.
- Return whether n ended up as 1.
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0) return false;
while (n % 2 == 0) n /= 2;
return n == 1;
}
}class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1class Solution {
public:
bool isPowerOfTwo(int n) {
if (n <= 0) return false;
while (n % 2 == 0) n /= 2;
return n == 1;
}
};function isPowerOfTwo(n) {
if (n <= 0) return false;
while (n % 2 === 0) n /= 2;
return n === 1;
}2Optimal (clear the lowest set bit)
O(1)One subtraction, one AND and one comparison.O(1)No extra memory.A positive power of two has exactly one 1 bit. n - 1 turns that bit off and sets every bit below it, so n & (n - 1) is 0 exactly when n had a single 1 bit. Checking n > 0 first rules out zero and the negative numbers.
- Return n > 0 and (n & (n - 1)) == 0.
class Solution {
public boolean 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)) == 0class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
};function isPowerOfTwo(n) {
return n > 0 && (n & (n - 1)) === 0;
}Edge cases to test
- n = 0 and negative numbers (never powers of two)
- n = 1, which is 2^0
- The largest power of two that fits in an int, 2^30
- The smallest int, -2^31, whose bit pattern has a single 1 bit but is negative
Hints
Hint 1
A power of two can be halved again and again until it reaches exactly 1, with no remainder along the way.
Hint 2
Look at the binary form: how many 1 bits does a power of two have?
Hint 3
Subtracting 1 from a number flips its lowest 1 bit and all the zeros below it. What does n & (n - 1) leave behind?
FAQ
What is the best time complexity for Power of Two?
Optimal (clear the lowest set bit) runs in O(1) time and O(1) extra space. One subtraction, one AND and one comparison.
Which pattern does Power of Two use?
It is a bit manipulation problem that uses the tricks to remember pattern. Other problems with the same pattern: Number of 1 Bits, Set the rightmost unset bit, XOR of 1 to n Numbers.
Is there a brute force solution for Power of Two?
Yes. Brute force (keep dividing by 2) takes O(log n) time and O(1) space. A positive number is a power of two exactly when dividing it by 2 repeatedly never leaves a remainder and ends at 1.
Which edge cases should I test for Power of Two?
n = 0 and negative numbers (never powers of two); n = 1, which is 2^0; The largest power of two that fits in an int, 2^30; The smallest int, -2^31, whose bit pattern has a single 1 bit but is negative.