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 == 2x.
Example 1:
Input: n = 1 Output: true Explanation: 20 = 1
Example 2:
Input: n = 16 Output: true Explanation: 24 = 16
Example 3:
Input: n = 3 Output: false
Constraints:
-231 <= n <= 231 - 1The #231 Power of Two problem asks you to determine whether a given integer can be represented as a power of 2. A key mathematical insight is that powers of two have only one set bit in their binary representation. For example, 1 (2^0), 2 (2^1), 4 (2^2), and 8 (2^3) each contain a single 1 in binary.
An efficient approach uses bit manipulation. If a number is a power of two, removing its lowest set bit results in zero. This property allows you to verify the condition with a constant-time bitwise check after confirming the number is positive.
Another way to think about the problem is through recursion or iterative division. If a number is repeatedly divisible by 2 until it becomes 1, it must be a power of two. While this approach is conceptually simple, the bit manipulation method is usually preferred in interviews due to its elegance and constant time complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bit Manipulation (single set-bit check) | O(1) | O(1) |
| Recursive / Iterative Division by 2 | O(log n) | O(1) iterative / O(log n) recursive |
Kevin Naughton Jr.
This approach involves continuously dividing the number n by 2. During each iteration, if n is divisible by 2, we continue the process. However, if n becomes 1 exactly, it's clear that the original n was a power of two. If n ever becomes an odd number greater than 1 during the division process, it means n is not a power of two.
The time complexity is O(log(n)) as we are dividing n by 2 each time. The space complexity is O(1) because no additional space is used.
1#include <stdbool.h>
2
3bool isPowerOfTwo(int n) {
4 if (n < 1) return false;
5 while (This C solution uses a while loop to divide n by 2 iteratively. If n reaches 1, it returns true; otherwise, it returns false.
This approach uses the property that if n is a power of two, then n & (n - 1) should be 0. This is because a power of two in binary form means there is only one '1' bit. Subtracting 1 from it flips all the bits after the last '1'. If the bitwise AND results in 0, n is a power of two.
The time complexity is O(1) because it's a constant-time operation, and the space complexity is also O(1).
1publicWatch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the Power of Two problem are common in coding interviews at major tech companies. Interviewers use it to test understanding of bit manipulation, number properties, and edge case handling.
The optimal approach uses a bit manipulation trick based on the binary representation of powers of two. Such numbers contain exactly one set bit, so removing the lowest set bit results in zero. This allows the check to be performed in constant time.
No special data structure is required for this problem. The solution mainly relies on mathematical properties and bit manipulation operations on integers, making it efficient and simple to implement.
A power of two has only one set bit in its binary form. When you subtract one from such a number, all lower bits flip, and applying a bitwise AND with the original number removes the set bit, producing zero.
Leveraging Java's bit manipulation capabilities, this solution offers a clean and efficient way to check for a power of two using bit operations.