Watch 10 video solutions for Power of Two, a easy level problem involving Math, Bit Manipulation, Recursion. This walkthrough by Kevin Naughton Jr. has 46,547 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |