This problem asks you to verify whether a number can be expressed as 2 raised to some integer exponent. GhostInterview emphasizes math insights and bit manipulation tricks to solve it quickly, including using n & (n - 1) to detect powers of two. Recursive checks can also confirm results by repeatedly dividing by two until reaching one.
Problem Statement
Given an integer n, determine whether it is a power of two. Return true if n equals 2 raised to some integer exponent x, otherwise return false. Negative numbers and zero are never powers of two.
For example, when n = 1, the function should return true because 2^0 = 1. If n = 16, return true because 2^4 = 16. If n = 3, return false since no integer x satisfies 2^x = 3. Input constraints are -2^31 <= n <= 2^31 - 1.
Examples
Example 1
Input: n = 1
Output: true
20 = 1
Example 2
Input: n = 16
Output: true
24 = 16
Example 3
Input: n = 3
Output: false
Example details omitted.
Constraints
- -231 <= n <= 231 - 1
Solution Approach
Bit Manipulation
Use the property that powers of two have exactly one bit set: n > 0 and n & (n - 1) == 0. This detects the single-bit pattern efficiently in O(1) time without loops.
Recursive Division
Recursively divide n by 2 and check if the result eventually equals 1. If n becomes odd before reaching 1, return false. This leverages the mathematical definition and highlights the pattern of repeated halving.
Mathematical Check with Log
Compute log2(n) and check if it is an integer. This approach ties directly to the exponent x in 2^x = n. It is less efficient than bit manipulation due to floating-point operations but validates the math pattern.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Bit manipulation runs in O(1) time and space. Recursive division can take O(log n) time with O(log n) stack space. Logarithmic checks run in O(1) but may incur floating-point precision overhead.
What Interviewers Usually Probe
- Clarifies whether negative numbers and zero should return false.
- Hints at using bit manipulation rather than iterative loops.
- Tests understanding of the mathematical pattern behind powers of two.
Common Pitfalls or Variants
Common pitfalls
- Not handling zero and negative inputs correctly, returning true incorrectly.
- Using iterative multiplication or division without stopping conditions, causing infinite loops.
- Relying on floating-point logs without tolerance, leading to incorrect results for large n.
Follow-up variants
- Check if a number is a power of three or five using a similar recursive or bit-mimicking approach.
- Return the largest power of two less than or equal to n using bit manipulation.
- Count how many numbers in an array are powers of two using the same n & (n - 1) trick.
How GhostInterview Helps
- Provides a step-by-step solver approach that immediately identifies the bit manipulation pattern for power-of-two detection.
- Highlights recursive strategies while showing their performance trade-offs and stack considerations.
- Generates quick test cases with explanations to validate edge inputs like 0, negative numbers, and maximum integer values.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the fastest way to check if a number is a power of two?
The fastest method is using bit manipulation: return n > 0 && (n & (n - 1)) == 0, which checks the single-bit pattern directly.
Can recursion be used to solve Power of Two efficiently?
Yes, recursion divides n by 2 repeatedly until reaching 1, but it uses O(log n) stack space compared to O(1) for bit manipulation.
Why does n & (n - 1) work for detecting powers of two?
Because powers of two have exactly one 1-bit in binary; subtracting 1 flips all lower bits, and ANDing with n clears the single 1-bit if it was a power of two.
Are negative numbers ever considered powers of two?
No, by definition, only positive integers of the form 2^x are powers of two, so negatives always return false.
Does using logarithms provide a reliable solution for large integers?
It works mathematically but may suffer from floating-point precision errors for very large integers, making bit manipulation safer.
Need direct help with Power of Two instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Power of Two from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Determine if a given integer is a power of four using math insights and bit manipulation tricks efficiently in code.
Open problem page#779 K-th Symbol in GrammarDetermine the K-th symbol in a recursively generated grammar table using math and bit manipulation patterns efficiently.
Open problem page#233 Number of Digit OneCompute the total number of digit one appearing in all numbers from 0 up to n using state transition dynamic programming for efficiency.
Open problem page