231. Power of Two - Solution & Explanation

The problem

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 == 2^x.

Example 1:

Input: n = 1
Output: true
Explanation: 2⁰ = 1

Example 2:

Input: n = 16
Output: true
Explanation: 2⁴ = 16

Example 3:

Input: n = 3
Output: false

Constraints:

-2³¹ <= n <= 2³¹ - 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.

Python

def is_power_of_two(n: int) -> bool:
    if n < 1:
        return False
    while n % 2 == 0:
        n //= 2
    return n == 1

Java

public class PowerOfTwo {
    public boolean isPowerOfTwo(int n) {
        if (n < 1) return false;
        while (n % 2 == 0) n /= 2;
        return n == 1;
    }
}

C++

#include <iostream>

bool isPowerOfTwo(int n) {
    if (n < 1) return false;
    while (n % 2 == 0) n /= 2;
    return n == 1;
}

JavaScript

function isPowerOfTwo(n) {
    if (n < 1) return false;
    while (n % 2 === 0) n /= 2;
    return n === 1;
}

#include <stdbool.h>

bool isPowerOfTwo(int n) {
    if (n < 1) return false;
    while (n % 2 == 0) n /= 2;
    return n == 1;
}

public class Solution {
    public bool IsPowerOfTwo(int n) {
        if (n < 1) return false;
        while (n % 2 == 0) n /= 2;
        return n == 1;
    }
}

This Python function performs an iterative division similar to the C/C++/Java solutions, refined with Python syntax.

Complexity

The time complexity is O(log(n)) and space complexity is O(1).

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.

Python

def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

Java

public class PowerOfTwo {
    public boolean isPowerOfTwo(int n) {
        return (n > 0) && ((n & (n - 1)) == 0);
    }
}

C++

#include <iostream>

bool isPowerOfTwo(int n) {
    return (n > 0) && ((n & (n - 1)) == 0);
}

JavaScript

function isPowerOfTwo(n) {
    return n > 0 && (n & (n - 1)) === 0;
}

#include <stdbool.h>

bool isPowerOfTwo(int n) {
    return (n > 0) && ((n & (n - 1)) == 0);
}

public class Solution {
    public bool IsPowerOfTwo(int n) {
        return (n > 0) && ((n & (n - 1)) == 0);
    }
}

In Python, this solution uses bitwise operations to efficiently check if n is a power of two.

Complexity

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

Try this approach in the editor

Approach 3: Bit Manipulation

According to the properties of bit manipulation, executing \texttt{n\&(n-1)} can eliminate the last bit 1 in the binary form of n. Therefore, if n > 0 and \texttt{n\&(n-1)} results in 0, then n is a power of 2.

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

TypeScript

function isPowerOfTwo(n: number): boolean {
    return n > 0 && (n & (n - 1)) === 0;
}

func isPowerOfTwo(n int) bool {
	return n > 0 && (n&(n-1)) == 0
}

Rust

impl Solution {
    pub fn is_power_of_two(n: i32) -> bool {
        n > 0 && (n & (n - 1)) == 0
    }
}

Try this approach in the editor

Approach 4: 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).

TypeScript

function isPowerOfTwo(n: number): boolean {
    return n > 0 && n === (n & -n);
}

func isPowerOfTwo(n int) bool {
	return n > 0 && n == (n&(-n))
}

Rust

impl Solution {
    pub fn is_power_of_two(n: i32) -> bool {
        n > 0 && n == (n & (-n))
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Iterative Division	The time complexity is O(log(n)) and space complexity is O(1).
Bit Manipulation	The time complexity remains at O(1), and space complexity is O(1).
Bit Manipulation	–
Lowbit	–

Complexity analysis

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.

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.

Power of Two solution and explanation

The problem

Approach overview

Approach 1: Iterative Division

Approach 2: Bit Manipulation

Approach 3: Bit Manipulation

Approach 4: Lowbit

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Power of Two solution and explanation

The problem

Approach overview

Approach 1: Iterative Division

Approach 2: Bit Manipulation

Approach 3: Bit Manipulation

Approach 4: Lowbit

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems