Problem Statement
Given a number, determine if it is a power of two. A number is a power of two if it can be expressed as ( 2^n ), where ( n ) is a non-negative integer.
Example
-
Input: n = 8
Output: true
Explanation: ( 8 = 2^3 ).
-
Input: n = 5
Output: false
Explanation: ( 5 ) is not a power of two.
-
Input: n = 1
Output: true
Explanation: ( 1 = 2^0 ).
Brute Force Approach
Approach
Idea: Repeatedly divide the number by 2 as long as it is divisible by 2. If the result eventually becomes 1, the number is a power of two.
Steps
- Handle the edge case where
n <= 0. Return false as negative numbers and 0 are not powers of two.
- While the number is greater than
1, check if it is divisible by 2.
- If not divisible, return
false.
- If the loop completes with the number becoming
1, return true.
Time & Space Complexity
- Time Complexity: O(log(n))
- The number is divided by
2 in each iteration.
- Space Complexity: O(1)
- Only a few variables are used.
Code Snippet
Dry Run
Input: n = 8
- Check if
n > 0: Yes.
- Loop through:
n = 8: Divisible by 2, divide to get n = 4.n = 4: Divisible by 2, divide to get n = 2.n = 2: Divisible by 2, divide to get n = 1.
- Return
true.
Efficient Approach Using Bit Manipulation
Approach
Idea: A number is a power of two if it has exactly one bit set in its binary representation. This can be checked using the property:
[ n & (n - 1) = 0 ]
This works because subtracting 1 from a power of two flips all the bits after the single 1 in its binary representation.
Steps
- Handle the edge case where
n <= 0. Return false.
- Use the bitwise
AND operation to check if ( n & (n - 1) = 0 ).
- Return the result.
Time & Space Complexity
- Time Complexity: O(1)
- The operation is constant-time.
- Space Complexity: O(1)
- Only a few variables are used.
Code Snippet
Dry Run
Input: n = 8
- Check if
n > 0: Yes.
- Compute ( 8 & (8 - 1) = 8 & 7 = 0 ).
- Return
true.
Complexity Analysis
| Operation | Brute Force | Efficient Approach |
|---|
| Time Complexity | O(log(n)) | O(1) |
| Space Complexity | O(1) | O(1) |
Conclusion
- The brute force approach is intuitive but may involve multiple iterations for large numbers.
- The efficient approach using bit manipulation is optimal and leverages properties of binary numbers to achieve constant time complexity.
- This problem highlights the power of understanding data representation in computers for optimization.