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 - 1Follow up: Could you solve it without loops/recursion?
Problem Overview: Given an integer n, determine whether it can be written as 2^k for some integer k. In other words, check if repeatedly dividing the number by 2 eventually reaches exactly 1 without leaving a remainder.
Approach 1: Iterative Division (Time: O(log n), Space: O(1))
This method repeatedly divides the number by 2 while it remains even. Start by rejecting non‑positive numbers because powers of two are always positive. Use a loop and check n % 2 == 0, dividing by 2 each iteration. If the process ends with n == 1, the original number is a power of two. The loop runs at most log2(n) times, making the time complexity O(log n) with constant memory.
Approach 2: Bit Manipulation (Time: O(1), Space: O(1))
A power of two has exactly one bit set in its binary representation. For example, 8 = 1000 and 16 = 10000. The expression n & (n - 1) clears the lowest set bit of n. If n is a power of two, subtracting 1 flips all lower bits and the bitwise AND becomes zero. The condition n > 0 && (n & (n - 1)) == 0 therefore identifies powers of two in constant time. This technique is common in bit manipulation problems and is the most efficient approach.
Approach 3: Recursive Halving (Time: O(log n), Space: O(log n))
The recursive variant mirrors the iterative logic. If n == 1, return true. If n is non‑positive or odd, return false. Otherwise call the function with n / 2. Each recursive step halves the number until reaching the base case. The recursion depth is proportional to log2(n), so the time complexity is O(log n) with O(log n) stack space. This version often appears when practicing recursion with simple mathematical checks.
Recommended for interviews: The bit manipulation solution is the expected answer. Interviewers want to see the insight that powers of two contain a single set bit and can be verified using n & (n - 1). Showing the iterative division approach first demonstrates understanding of the math behind powers of two, but the constant‑time bit trick shows stronger problem‑solving skill.
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.
This C solution uses a while loop to divide n by 2 iteratively. If n reaches 1, it returns true; otherwise, it returns false.
C++
Java
Python
C#
JavaScript
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.
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.
This solution uses bit manipulation by employing the expression n & (n - 1) which is efficient and direct for determining if n is a power of two.
C++
Java
Python
C#
JavaScript
The time complexity is O(1) because it's a constant-time operation, and the space complexity is also O(1).
| Approach | Complexity |
|---|---|
| Iterative Division | The time complexity is O(log(n)) as we are dividing |
| Bit Manipulation | The time complexity is O(1) because it's a constant-time operation, and the space complexity is also O(1). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Division | O(log n) | O(1) | When demonstrating the mathematical definition of powers of two or when bit tricks are not expected. |
| Bit Manipulation (n & (n-1)) | O(1) | O(1) | Preferred interview solution. Fast constant‑time check using binary representation. |
| Recursive Halving | O(log n) | O(log n) | Useful for practicing recursion or expressing the divide‑by‑two logic recursively. |
Power of Two • Kevin Naughton Jr. • 46,547 views views
Watch 9 more video solutions →Practice Power of Two with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor