Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Power of Two

EASYProblemSolveExternal Links

Description

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.

Powers of two form the sequence: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, …

Note that 1 is a power of two (2⁰ = 1), and non-positive numbers are never powers of two.

Examples

Example 1

Input: n = 1

Output: true

Explanation: 2⁰ = 1, so 1 is a power of two.

Example 2

Input: n = 16

Output: true

Explanation: 2⁴ = 16, so 16 is a power of two.

Example 3

Input: n = 3

Output: false

Explanation: There is no integer x such that 2^x = 3. The closest powers of two are 2¹ = 2 and 2² = 4.

Constraints

  • -2^31 ≤ n ≤ 2^31 - 1

Editorial

Brute Force

Intuition

The most straightforward approach is to directly test the definition: if n is a power of two, then we can repeatedly divide it by 2 and eventually reach exactly 1.

If at any point during the division n becomes odd (i.e., n % 2 ≠ 0) while still being greater than 1, then n cannot be a power of two. For example:

  • 16 → 8 → 4 → 2 → 1 ✓ (all steps are even divisions)
  • 6 → 3 ✗ (3 is odd and not 1, so 6 is not a power of two)

We must also handle edge cases: any non-positive number (n ≤ 0) is never a power of two, since 2^x is always positive for any integer x.

Think of it like peeling away factors of 2 one at a time. A power of two is composed entirely of 2s — if any other prime factor is present, the peeling process will expose it as an odd number before reaching 1.

Step-by-Step Explanation

Let's trace through with n = 16 (Example 2):

Step 1: Check if n ≤ 0: 16 > 0 ✓. Proceed.

Step 2: Is n > 1? Yes (16 > 1). Check n % 2: 16 % 2 = 0 (even). Divide: n = 16 / 2 = 8.

Step 3: Is n > 1? Yes (8 > 1). Check n % 2: 8 % 2 = 0 (even). Divide: n = 8 / 2 = 4.

Step 4: Is n > 1? Yes (4 > 1). Check n % 2: 4 % 2 = 0 (even). Divide: n = 4 / 2 = 2.

Step 5: Is n > 1? Yes (2 > 1). Check n % 2: 2 % 2 = 0 (even). Divide: n = 2 / 2 = 1.

Step 6: Is n > 1? No (n = 1). Exit loop.

Step 7: n == 1, so return true. 16 is a power of two.

Now let's trace n = 6:

Step 1: 6 > 0 ✓.
Step 2: 6 > 1 and 6 % 2 = 0 → n = 3.
Step 3: 3 > 1 but 3 % 2 = 1 (odd!) → Return false immediately. 6 is NOT a power of two.

And n = 1:
Step 1: 1 > 0 ✓. Loop condition: 1 > 1 is false → skip loop. Return true (2⁰ = 1).

Repeated Division — Peeling Away Factors of 2 — Watch how repeatedly dividing n=16 by 2 right-shifts the single set bit through the binary representation until it reaches position 0 (value 1), confirming it is a power of two.

Algorithm

  1. If n ≤ 0, return false (powers of two are always positive)
  2. While n > 1:
    a. If n % 2 ≠ 0 (n is odd), return false — n has a factor other than 2
    b. Divide n by 2: n = n / 2
  3. If we exit the loop, n == 1, so return true

Code

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;
        while (n > 1) {
            if (n % 2 != 0) return false;
            n /= 2;
        }
        return true;
    }
};
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        while n > 1:
            if n % 2 != 0:
                return False
            n //= 2
        return True
class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        while (n > 1) {
            if (n % 2 != 0) return false;
            n /= 2;
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(log n)

In the worst case (when n is a power of 2), we divide n by 2 repeatedly until it becomes 1. Since we halve n each time, the loop runs at most log₂(n) times. For n = 2³¹ - 1 (the maximum positive integer), this is at most 31 iterations.

Space Complexity: O(1)

We only use a single variable and modify it in place. No additional data structures are needed.

While O(log n) is efficient in practice (at most 31 iterations for 32-bit integers), we can do better. There exists an O(1) solution that checks the answer in constant time using a single bit manipulation operation — no loops at all.

Why This Approach Is Not Efficient

The repeated division approach works correctly but uses a loop that runs O(log n) times. While this is fast in practice (at most 31 iterations for a 32-bit integer), there is a key observation about powers of two that enables a constant-time solution:

Binary Insight: A power of two has exactly one bit set in its binary representation.

  • 1 = 00001
  • 2 = 00010
  • 4 = 00100
  • 8 = 01000
  • 16 = 10000

Every power of two is a single 1 followed by zeros. This is not a coincidence — multiplying by 2 shifts bits left, and 2⁰ = 1 starts with a single bit, so all powers of 2 maintain exactly one set bit.

Non-powers of two have multiple bits set:

  • 3 = 011
  • 6 = 110
  • 7 = 111

If we could check "does this number have exactly one set bit?" in O(1) time, we could skip the loop entirely. It turns out there is a famous bit manipulation trick that does exactly this: the expression n & (n - 1) clears the lowest set bit of n. If n has exactly one set bit (i.e., it is a power of two), then clearing it produces 0.

Optimal Approach - Bit Manipulation (n & (n-1))

Intuition

The key insight is that a power of two has a unique property in binary: it has exactly one bit set to 1, and all other bits are 0.

Now consider what happens when we subtract 1 from a power of two:

  • n = 16 = 10000
  • n - 1 = 15 = 01111

Subtracting 1 flips the single set bit to 0 and turns all the lower bits (which were 0) into 1. The result is that n and n-1 have no bits in common — they are bitwise complements in the relevant positions.

Therefore: n & (n - 1) = 10000 & 01111 = 00000 = 0

For a non-power of two, this doesn't happen:

  • n = 6 = 110
  • n - 1 = 5 = 101
  • n & (n-1) = 100 = 4 ≠ 0

Because 6 has more than one set bit, clearing the lowest one (the rightmost 1) still leaves other bits set.

So the complete check is: n is a power of two if and only if n > 0 and n & (n - 1) == 0.

The n > 0 check is necessary because 0 & (-1) would also equal 0 in some representations, and negative numbers are never powers of two.

This is one of the most elegant bit manipulation tricks in computer science — it reduces what seems like a loop problem to a single AND operation.

Step-by-Step Explanation

Let's trace through with n = 16 (Example 2):

Step 1: Check n > 0: 16 > 0 ✓. Proceed to bit check.

Step 2: Write n in binary: 16 = 10000. Observe: exactly one bit is set (at position 4).

Step 3: Compute n - 1 = 15. Write in binary: 15 = 01111. The single set bit flipped to 0, and all lower bits flipped to 1.

Step 4: Compute n & (n-1): 10000 & 01111. Compare each bit position:

  • Bit 4: 1 & 0 = 0
  • Bit 3: 0 & 1 = 0
  • Bit 2: 0 & 1 = 0
  • Bit 1: 0 & 1 = 0
  • Bit 0: 0 & 1 = 0

Step 5: Result = 00000 = 0. Since n > 0 AND n & (n-1) == 0, return true.

Now let's trace n = 6 (a non-power):

Step 1: 6 > 0 ✓.
Step 2: 6 in binary = 110. Two bits are set.
Step 3: n - 1 = 5 = 101.
Step 4: 110 & 101 = 100 = 4.
Step 5: 4 ≠ 0, so return false. The AND didn't clear all bits because there were multiple set bits to begin with.

And n = 1:
Step 1: 1 > 0 ✓.
Step 2: 1 in binary = 1.
Step 3: n - 1 = 0 = 0.
Step 4: 1 & 0 = 0.
Step 5: 0 == 0, return true. (2⁰ = 1 is indeed a power of two.)

Bit Trick — n & (n-1) Clears the Lone Set Bit — Watch how the binary representation of n=16 (10000) and n-1=15 (01111) have zero bits in common, making their AND result exactly 0 — the hallmark of a power of two.

Algorithm

  1. Check if n > 0. If not, return false (non-positive numbers are never powers of two).
  2. Compute n & (n - 1).
  3. If the result is 0, return true — n has exactly one set bit, so it is a power of two.
  4. Otherwise, return false — n has more than one set bit.

Code

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0
class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

Complexity Analysis

Time Complexity: O(1)

The solution performs exactly three operations regardless of the input size: one comparison (n > 0), one subtraction (n - 1), and one bitwise AND (n & (n-1)). All three are constant-time operations.

Space Complexity: O(1)

No additional memory is used. The computation happens entirely on the input value with no extra data structures.

Why this is optimal: We cannot do better than O(1) time and O(1) space. The bit trick n & (n-1) leverages a fundamental property of binary representation — that a power of two has exactly one set bit, and subtracting 1 flips exactly that bit and all lower bits. This transforms a seemingly iterative problem into a single arithmetic check. The follow-up in the problem asks "Can you solve it without loops/recursion?" — and this one-liner is the answer.