Language Selection
Choose your preferred programming language
Showing: Python
Power of Two
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^x.
Examples
Example 1:
Input: n = 1
Output: true
Explanation: 2^0 = 1
Example 2:
Input: n = 16
Output: true
Explanation: 2^4 = 16
Example 3:
Input: n = 3
Output: false
Explanation: 3 is not a power of two.
Example 4:
Input: n = 0
Output: false
Explanation: 0 is not a power of two.
Constraints
-2^31 <= n <= 2^31 - 1
Approach 1: Bit Manipulation (Optimal)
Algorithm
A power of two has exactly one bit set in its binary representation. Use n & (n-1) == 0 to check this property.
Steps:
- Check if n > 0 (powers of two are positive)
- Check if n & (n-1) == 0 (only one bit set)
Implementation
Python:
def isPowerOfTwo(n):
"""
Check if n is a power of two using bit manipulation
Time: O(1)
Space: O(1)
"""
return n > 0 and n & (n - 1) == 0
Java:
class Solution {
/**
* Check if n is a power of two using bit manipulation
* Time: O(1)
* Space: O(1)
*/
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}
Go:
func isPowerOfTwo(n int) bool {
/**
* Check if n is a power of two using bit manipulation
* Time: O(1)
* Space: O(1)
*/
return n > 0 && n&(n-1) == 0
}
JavaScript:
/**
* Check if n is a power of two using bit manipulation
* Time: O(1)
* Space: O(1)
*/
function isPowerOfTwo(n) {
return n > 0 && (n & (n - 1)) === 0;
}
C#:
public class Solution {
/// <summary>
/// Check if n is a power of two using bit manipulation
/// Time: O(1)
/// Space: O(1)
/// </summary>
public bool IsPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}
Complexity Analysis
- Time Complexity: O(1) - Constant time bit operations
- Space Complexity: O(1) - No extra space used
Approach 2: Logarithm (Alternative)
Algorithm
Use logarithm to check if log2(n) is an integer.
Steps:
- Check if n > 0
- Calculate log2(n)
- Check if the result is an integer
Implementation
Python:
import math
def isPowerOfTwo_log(n):
"""
Check if n is a power of two using logarithm
Time: O(1)
Space: O(1)
"""
if n <= 0:
return False
log_result = math.log2(n)
return log_result == int(log_result)
# Alternative using math.log
def isPowerOfTwo_log_alt(n):
"""
Check if n is a power of two using math.log
Time: O(1)
Space: O(1)
"""
if n <= 0:
return False
log_result = math.log(n) / math.log(2)
return abs(log_result - round(log_result)) < 1e-10
Java:
class Solution {
/**
* Check if n is a power of two using logarithm
* Time: O(1)
* Space: O(1)
*/
public boolean isPowerOfTwoLog(int n) {
if (n <= 0) {
return false;
}
double logResult = Math.log(n) / Math.log(2);
return Math.abs(logResult - Math.round(logResult)) < 1e-10;
}
}
Go:
import "math"
func isPowerOfTwoLog(n int) bool {
/**
* Check if n is a power of two using logarithm
* Time: O(1)
* Space: O(1)
*/
if n <= 0 {
return false
}
logResult := math.Log(float64(n)) / math.Log(2)
return math.Abs(logResult-math.Round(logResult)) < 1e-10
}
JavaScript:
/**
* Check if n is a power of two using logarithm
* Time: O(1)
* Space: O(1)
*/
function isPowerOfTwoLog(n) {
if (n <= 0) {
return false;
}
const logResult = Math.log2(n);
return logResult === Math.floor(logResult);
}
C#:
using System;
public class Solution {
/// <summary>
/// Check if n is a power of two using logarithm
/// Time: O(1)
/// Space: O(1)
/// </summary>
public bool IsPowerOfTwoLog(int n) {
if (n <= 0) {
return false;
}
double logResult = Math.Log(n) / Math.Log(2);
return Math.Abs(logResult - Math.Round(logResult)) < 1e-10;
}
}
Complexity Analysis
- Time Complexity: O(1) - Constant time logarithm calculation
- Space Complexity: O(1) - No extra space used
Approach 3: Division (Alternative)
Algorithm
Keep dividing n by 2 until it becomes 1 or an odd number.
Steps:
- Check if n > 0
- While n is even, divide by 2
- Return true if n becomes 1
Implementation
Python:
def isPowerOfTwo_division(n):
"""
Check if n is a power of two using division
Time: O(log n)
Space: O(1)
"""
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1
Java:
class Solution {
/**
* Check if n is a power of two using division
* Time: O(log n)
* Space: O(1)
*/
public boolean isPowerOfTwoDivision(int n) {
if (n <= 0) {
return false;
}
while (n % 2 == 0) {
n /= 2;
}
return n == 1;
}
}
Go:
func isPowerOfTwoDivision(n int) bool {
/**
* Check if n is a power of two using division
* Time: O(log n)
* Space: O(1)
*/
if n <= 0 {
return false
}
for n%2 == 0 {
n /= 2
}
return n == 1
}
JavaScript:
/**
* Check if n is a power of two using division
* Time: O(log n)
* Space: O(1)
*/
function isPowerOfTwoDivision(n) {
if (n <= 0) {
return false;
}
while (n % 2 === 0) {
n /= 2;
}
return n === 1;
}
C#:
public class Solution {
/// <summary>
/// Check if n is a power of two using division
/// Time: O(log n)
/// Space: O(1)
/// </summary>
public bool IsPowerOfTwoDivision(int n) {
if (n <= 0) {
return false;
}
while (n % 2 == 0) {
n /= 2;
}
return n == 1;
}
}
Complexity Analysis
- Time Complexity: O(log n) - At most log n divisions
- Space Complexity: O(1) - No extra space used
Approach 4: Count Set Bits (Alternative)
Algorithm
Count the number of set bits in the binary representation. A power of two has exactly one set bit.
Steps:
- Check if n > 0
- Count set bits in n
- Return true if count is 1
Implementation
Python:
def isPowerOfTwo_countBits(n):
"""
Check if n is a power of two by counting set bits
Time: O(log n)
Space: O(1)
"""
if n <= 0:
return False
count = 0
while n:
count += n & 1
n >>= 1
return count == 1
# Using built-in function
def isPowerOfTwo_countBits_builtin(n):
"""
Check if n is a power of two using built-in bit count
Time: O(1)
Space: O(1)
"""
return n > 0 and bin(n).count('1') == 1
Java:
class Solution {
/**
* Check if n is a power of two by counting set bits
* Time: O(log n)
* Space: O(1)
*/
public boolean isPowerOfTwoCountBits(int n) {
if (n <= 0) {
return false;
}
int count = 0;
while (n > 0) {
count += n & 1;
n >>= 1;
}
return count == 1;
}
/**
* Using built-in bit count
* Time: O(1)
* Space: O(1)
*/
public boolean isPowerOfTwoCountBitsBuiltin(int n) {
return n > 0 && Integer.bitCount(n) == 1;
}
}
Go:
func isPowerOfTwoCountBits(n int) bool {
/**
* Check if n is a power of two by counting set bits
* Time: O(log n)
* Space: O(1)
*/
if n <= 0 {
return false
}
count := 0
for n > 0 {
count += n & 1
n >>= 1
}
return count == 1
}
// Using built-in function
func isPowerOfTwoCountBitsBuiltin(n int) bool {
/**
* Check if n is a power of two using built-in bit count
* Time: O(1)
* Space: O(1)
*/
return n > 0 && bits.OnesCount(uint(n)) == 1
}
JavaScript:
/**
* Check if n is a power of two by counting set bits
* Time: O(log n)
* Space: O(1)
*/
function isPowerOfTwoCountBits(n) {
if (n <= 0) {
return false;
}
let count = 0;
while (n > 0) {
count += n & 1;
n >>= 1;
}
return count === 1;
}
/**
* Using built-in function
* Time: O(1)
* Space: O(1)
*/
function isPowerOfTwoCountBitsBuiltin(n) {
return n > 0 && (n.toString(2).match(/1/g) || []).length === 1;
}
C#:
using System.Numerics;
public class Solution {
/// <summary>
/// Check if n is a power of two by counting set bits
/// Time: O(log n)
/// Space: O(1)
/// </summary>
public bool IsPowerOfTwoCountBits(int n) {
if (n <= 0) {
return false;
}
int count = 0;
while (n > 0) {
count += n & 1;
n >>= 1;
}
return count == 1;
}
/// <summary>
/// Using built-in bit count
/// Time: O(1)
/// Space: O(1)
/// </summary>
public bool IsPowerOfTwoCountBitsBuiltin(int n) {
return n > 0 && BitOperations.PopCount((uint)n) == 1;
}
}
Complexity Analysis
- Time Complexity: O(log n) - At most log n bits to check
- Space Complexity: O(1) - No extra space used
Key Insights
- Bit Pattern: Powers of two have exactly one bit set
- n & (n-1) Trick: Clears the rightmost set bit
- Logarithm Property: log2(n) is integer for powers of two
- Division Method: Keep dividing by 2 until odd
- Bit Counting: Count set bits, should be exactly 1
Edge Cases
- Zero: 0 is not a power of two
- Negative Numbers: Negative numbers are not powers of two
- One: 1 is 2^0, so it’s a power of two
- Large Numbers: Handle 2^30, 2^31 correctly
- Non-Powers: Numbers like 3, 5, 6 are not powers of two
Test Cases
def test_isPowerOfTwo():
# Powers of two
assert isPowerOfTwo(1) == True
assert isPowerOfTwo(2) == True
assert isPowerOfTwo(4) == True
assert isPowerOfTwo(8) == True
assert isPowerOfTwo(16) == True
assert isPowerOfTwo(32) == True
assert isPowerOfTwo(64) == True
assert isPowerOfTwo(128) == True
assert isPowerOfTwo(256) == True
assert isPowerOfTwo(512) == True
assert isPowerOfTwo(1024) == True
# Non-powers of two
assert isPowerOfTwo(0) == False
assert isPowerOfTwo(3) == False
assert isPowerOfTwo(5) == False
assert isPowerOfTwo(6) == False
assert isPowerOfTwo(7) == False
assert isPowerOfTwo(9) == False
assert isPowerOfTwo(10) == False
assert isPowerOfTwo(15) == False
assert isPowerOfTwo(17) == False
assert isPowerOfTwo(33) == False
# Edge cases
assert isPowerOfTwo(-1) == False
assert isPowerOfTwo(-2) == False
assert isPowerOfTwo(-4) == False
print("All tests passed!")
test_isPowerOfTwo()
Follow-up Questions
- Power of Three: Check if a number is a power of three?
- Power of Four: Check if a number is a power of four?
- Next Power of Two: Find the next power of two greater than n?
- Previous Power of Two: Find the previous power of two less than n?
- All Powers of Two: Generate all powers of two up to n?
Common Mistakes
- Not Handling Zero: Forgetting that 0 is not a power of two
- Negative Numbers: Not checking for negative inputs
- Floating Point Precision: Issues with logarithm approach
- Integer Overflow: Problems with large numbers
- Bit Manipulation: Incorrect use of bit operations
Interview Tips
- Start with Bit Manipulation: Most efficient O(1) solution
- Explain the Trick:
n & (n-1)clears rightmost set bit - Discuss Alternatives: Show knowledge of different approaches
- Handle Edge Cases: Mention zero and negative numbers
- Follow-up Ready: Be prepared for power of three/four
Concept Explanations
Bit Manipulation Trick: The expression n & (n-1) clears the rightmost set bit in n. For powers of two, this results in 0 because powers of two have exactly one set bit. For example:
- 8 (1000) & 7 (0111) = 0000
- 16 (10000) & 15 (01111) = 00000
Why This Works: Powers of two in binary have exactly one bit set (the leftmost bit). When we subtract 1 from a power of two, all bits to the right of that set bit become 1, and the set bit becomes 0. The AND operation then results in 0.
Logarithm Approach: If n is a power of two, then log2(n) should be an integer. We can check this by calculating the logarithm and verifying it’s a whole number.
Division Method: We can repeatedly divide by 2 until we get an odd number. If the result is 1, then the original number was a power of two.
Bit Counting: Powers of two have exactly one bit set in their binary representation. We can count the set bits and check if the count is 1.