231. Power of Two - Explanation

Description

You are 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^0) is 1.

Example 2:

Input: n = 8

Output: true

Explanation: (2^3) is 8.

Example 3:

Input: n = 12

Output: false

Constraints:

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Bit Manipulation - Understanding binary representation of numbers and bitwise operators (AND, OR, shifts) is essential for the optimal solutions
Recursion - The recursive approach divides the problem by 2 at each step until reaching the base case
Two's Complement - Understanding how negative numbers are represented helps explain why n & (-n) isolates the lowest set bit

1. Brute Force

Intuition

We can generate all powers of two by starting from 1 and repeatedly multiplying by 2. If we reach exactly n, then n is a power of two. If we exceed n without matching it, then it's not.

Algorithm

If n is less than or equal to 0, return false.
Start with x = 1.
While x is less than n, multiply x by 2.
Return true if x equals n, false otherwise.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False

        x = 1
        while x < n:
            x *= 2
        return x == n

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;

        long x = 1;
        while (x < n) {
            x *= 2;
        }
        return x == n;
    }
}

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;

        long long x = 1;
        while (x < n) {
            x *= 2;
        }
        return x == n;
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {boolean}
     */
    isPowerOfTwo(n) {
        if (n <= 0) return false;

        let x = 1;
        while (x < n) {
            x *= 2;
        }
        return x === n;
    }
}

public class Solution {
    public bool IsPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }

        int x = 1;
        while (x < n) {
            x *= 2;
        }
        return x == n;
    }
}

class Solution {
    fun isPowerOfTwo(n: Int): Boolean {
        if (n <= 0) return false

        var x = 1L
        while (x < n) {
            x *= 2
        }
        return x == n.toLong()
    }
}

class Solution {
    func isPowerOfTwo(_ n: Int) -> Bool {
        if n <= 0 {
            return false
        }

        var x = 1
        while x < n {
            x *= 2
        }
        return x == n
    }
}

impl Solution {
    pub fn is_power_of_two(n: i32) -> bool {
        if n <= 0 {
            return false;
        }
        let mut x: i64 = 1;
        while x < n as i64 {
            x *= 2;
        }
        x == n as i64
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

2. Recursion

Intuition

A number is a power of two if we can repeatedly divide it by 2 until we reach 1. If at any point the number is odd (and not 1), it cannot be a power of two.

This recursive approach reduces the problem by half at each step.

Algorithm

If n equals 1, return true (2^0 = 1).
If n is less than or equal to 0, or n is odd, return false.
Recursively check if n / 2 is a power of two.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n == 1:
            return True
        if n <= 0 or n % 2 == 1:
            return False
        return self.isPowerOfTwo(n // 2)

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

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n == 1) {
            return true;
        }
        if (n <= 0 || n % 2 == 1) {
            return false;
        }
        return isPowerOfTwo(n / 2);
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {boolean}
     */
    isPowerOfTwo(n) {
        if (n === 1) {
            return true;
        }
        if (n <= 0 || n % 2 === 1) {
            return false;
        }
        return this.isPowerOfTwo(Math.floor(n / 2));
    }
}

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

class Solution {
    fun isPowerOfTwo(n: Int): Boolean {
        if (n == 1) {
            return true
        }
        if (n <= 0 || n % 2 == 1) {
            return false
        }
        return isPowerOfTwo(n / 2)
    }
}

class Solution {
    func isPowerOfTwo(_ n: Int) -> Bool {
        if n == 1 {
            return true
        }
        if n <= 0 || n % 2 == 1 {
            return false
        }
        return isPowerOfTwo(n / 2)
    }
}

impl Solution {
    pub fn is_power_of_two(n: i32) -> bool {
        if n == 1 {
            return true;
        }
        if n <= 0 || n % 2 == 1 {
            return false;
        }
        Self::is_power_of_two(n / 2)
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$ for recursion stack.

3. Iteration

Intuition

The same logic as recursion, but implemented with a loop. We keep dividing by 2 (or right-shifting by 1) as long as the number is even. If we end up with 1, the original number was a power of two.

Algorithm

If n is less than or equal to 0, return false.
While n is even (divisible by 2), right-shift n by 1.
Return true if n equals 1, false otherwise.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False

        while n % 2 == 0:
            n >>= 1
        return n == 1

class Solution {
    /**
     * @param {number} n
     * @return {boolean}
     */
    isPowerOfTwo(n) {
        if (n <= 0) return 0;

        while (n % 2 === 0) {
            n >>= 1;
        }
        return n === 1;
    }
}

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

class Solution {
    fun isPowerOfTwo(n: Int): Boolean {
        if (n <= 0) return false

        var num = n
        while (num % 2 == 0) {
            num = num shr 1
        }
        return num == 1
    }
}

class Solution {
    func isPowerOfTwo(_ n: Int) -> Bool {
        if n <= 0 {
            return false
        }

        var num = n
        while num % 2 == 0 {
            num >>= 1
        }
        return num == 1
    }
}

impl Solution {
    pub fn is_power_of_two(n: i32) -> bool {
        if n <= 0 {
            return false;
        }
        let mut n = n;
        while n % 2 == 0 {
            n >>= 1;
        }
        n == 1
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

4. Bit Manipulation - I

Intuition

In two's complement representation, -n flips all bits of n and adds 1. For a power of two (which has exactly one set bit), n & (-n) isolates the lowest set bit. If n is a power of two, this equals n itself since there's only one bit set.

Algorithm

Check that n is positive.
Compute n & (-n) to isolate the lowest set bit.
Return true if this equals n, meaning n has exactly one set bit.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (-n)) == n

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

5. Bit Manipulation - II

Intuition

Powers of two in binary have exactly one bit set (1, 10, 100, 1000, ...). Subtracting 1 from such a number flips all bits from the rightmost set bit onward. For example, 8 (1000) minus 1 equals 7 (0111).

ANDing n with n - 1 clears the lowest set bit. If n is a power of two, this results in 0 since there was only one bit to clear.

Algorithm

Check that n is positive.
Compute n & (n - 1) to clear the lowest set bit.
Return true if the result is 0, meaning n had exactly one set bit.

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

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

6. Math

Intuition

The largest power of two that fits in a 32-bit signed integer is 2^30 (since 2^31 exceeds the positive range). Any smaller power of two must divide evenly into 2^30.

If n is a power of two, then 2^30 mod n equals 0. If n is not a power of two, the division will have a remainder.

Algorithm

Check that n is positive.
Compute (1 << 30) % n (i.e., 2^30 mod n).
Return true if the result is 0.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and ((1 << 30) % n) == 0

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting to Handle Non-Positive Numbers

A common mistake is forgetting that n must be strictly positive. Zero and negative numbers cannot be powers of two, but the bit manipulation tricks like n & (n - 1) == 0 will incorrectly return true for n = 0. Always check n > 0 before applying bit operations.

Integer Overflow in Iterative Approaches

When iteratively multiplying by 2 (e.g., x *= 2), the variable can overflow if using a 32-bit integer type. In languages like Java or C++, use a long or long long type for the accumulator to avoid wrapping around to negative values before reaching large inputs like 2^30.