Skip to main content
Talentd

Power of Two - Solution & Explanation

EasyMathBit ManipulationRecursion13 min readAsked at: Amazon, Microsoft, Goldman Sachs +8
Practice this problem

Problem Statement

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 - 1

 

Follow up: Could you solve it without loops/recursion?

Approach Overview

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 1: Iterative Division

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Bit Manipulation

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.

Code

CC++JavaPythonC#JavaScriptGoTypeScriptRust

C

C++

Java

Python

C#

JavaScript

Go

TypeScript

Rust

Complexity

The time complexity is O(1) because it's a constant-time operation, and the space complexity is also O(1).

Try this approach in the editor →

Approach 3: Lowbit

According to the definition of lowbit, we know that lowbit(x) = x \& (-x), which can get the decimal number represented by the last bit 1 of n. Therefore, if n > 0 and lowbit(n) equals n, then n is a power of 2.

The time complexity is O(1), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Division

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.

Bit Manipulation

The time complexity is O(1) because it's a constant-time operation, and the space complexity is also O(1).

Lowbit—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative DivisionO(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 HalvingO(log n)O(log n)Useful for practicing recursion or expressing the divide‑by‑two logic recursively.

Video Solution

Power of 2 | Leetcode #231 | 4 methods explained • Techdose • 43,485 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Power of Two easy or hard?
Power of Two is classified as an Easy problem on LeetCode. The straightforward solution uses repeated division, while the more optimal approach uses a simple bit manipulation trick. The challenge mainly tests understanding of binary representation.
How to solve Power of Two in O(1)?
Use the bit trick `n & (n - 1)`. For any power of two, the binary representation contains a single set bit. Subtracting 1 flips that bit and all lower bits, and the AND operation clears it. If `n > 0` and the result equals 0, the number is a power of two.
Power of Two Python or Java solution
In Python or Java, the typical implementation checks `n > 0 and (n & (n - 1)) == 0`. Both languages support bitwise AND operations directly, making the implementation just a single condition inside a function.
What is the best approach for Power of Two?
The bit manipulation check `n > 0 && (n & (n - 1)) == 0` is the best approach. A power of two has exactly one set bit in binary, and the expression removes the lowest set bit. If the result becomes zero, the number had only one bit set. This runs in O(1) time and O(1) space.
What data structure is used in Power of Two?
No complex data structures are required. The optimal solution relies on bitwise operations from bit manipulation. Simpler implementations may only use arithmetic operations such as division and modulo.
What is the time complexity of Power of Two?
The optimal bit manipulation solution runs in O(1) time because it performs only a few constant bit operations. The iterative or recursive division approaches run in O(log n) time since the number is repeatedly divided by 2 until it reaches 1 or becomes odd.
Is Power of Two asked at Google, Amazon, or Meta?
Power of Two is a common warm‑up question used by companies like Amazon, Google, and Meta to evaluate basic bit manipulation knowledge. It frequently appears in early interview rounds or coding screens where understanding binary representation is tested.

Ready to solve this problem?

Practice Power of Two with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of 1 Bits

Next

Power of Four