LeetCodee

231. Power of Two

Jump to Solution: Python Java C++ JavaScript C#

Problem 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ˣ.

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?

Solution

Python Solution

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        # A power of two has exactly one '1' bit
        # n & (n-1) removes the rightmost '1' bit
        return n > 0 and (n & (n-1)) == 0

Time Complexity: O(1)

Bitwise operations take constant time.

Space Complexity: O(1)

Only uses a constant amount of space.

Java Solution

class Solution {
    public boolean isPowerOfTwo(int n) {
        // A power of two has exactly one '1' bit
        // n & (n-1) removes the rightmost '1' bit
        return n > 0 && (n & (n-1)) == 0;
    }
}

Time Complexity: O(1)

Bitwise operations take constant time.

Space Complexity: O(1)

Only uses a constant amount of space.

C++ Solution

class Solution {
public:
    bool isPowerOfTwo(int n) {
        // A power of two has exactly one '1' bit
        // n & (n-1) removes the rightmost '1' bit
        return n > 0 && (n & (n-1)) == 0;
    }
};

Time Complexity: O(1)

Bitwise operations take constant time.

Space Complexity: O(1)

Only uses a constant amount of space.

JavaScript Solution

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function(n) {
    // A power of two has exactly one '1' bit
    // n & (n-1) removes the rightmost '1' bit
    return n > 0 && (n & (n-1)) === 0;
};

Time Complexity: O(1)

Bitwise operations take constant time.

Space Complexity: O(1)

Only uses a constant amount of space.

C# Solution

public class Solution {
    public bool IsPowerOfTwo(int n) {
        // A power of two has exactly one '1' bit
        // n & (n-1) removes the rightmost '1' bit
        return n > 0 && (n & (n-1)) == 0;
    }
}

Time Complexity: O(1)

Bitwise operations take constant time.

Space Complexity: O(1)

Only uses a constant amount of space.

Approach Explanation

The solution uses a bit manipulation trick to determine if a number is a power of two. Here's how it works:

  1. Key Properties:
    • Powers of two in binary have exactly one '1' bit
    • Examples: 1 (1), 2 (10), 4 (100), 8 (1000), 16 (10000)
    • n-1 will have all bits to the right of that '1' set to 1
  2. Bit Manipulation:
    • n & (n-1) removes the rightmost '1' bit
    • For powers of two, this should result in 0
    • We also check n > 0 to handle negative numbers and zero

Alternative approaches:

  • Loop approach: Repeatedly divide by 2 and check remainder
  • Logarithmic approach: Check if log₂(n) is an integer
  • Bit counting approach: Count number of '1' bits
  • The bit manipulation approach is most efficient