Code Implementation

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

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

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

var isPowerOfTwo = function(n) {
    if (n <= 0) return false;
    return (n & (n - 1)) === 0;
};
      

Problem Description

You are given an integer n. Your task is to determine whether n is a power of two. In other words, check if there exists an integer x such that n == 2x where x is an integer and x ≥ 0.

Key constraints:

• n can be positive, zero, or negative.
• Return true if n is a power of two, otherwise return false.

Thought Process

The first idea is to check all powers of two up to n and see if any of them equal n. This would work, but it is inefficient, especially for large numbers.

Next, we consider properties of binary numbers. A power of two in binary always has exactly one bit set (for example, 1 is 0001, 2 is 0010, 4 is 0100, etc). This unique property allows us to check if n is a power of two much more efficiently using bitwise operations.

We also need to handle negative numbers and zero, since powers of two are always positive.

Solution Approach

We can use a bit manipulation trick to solve this problem efficiently:

• First, check if n is positive. If not, return false.
• For a positive integer n, if n is a power of two, its binary representation contains exactly one 1 and the rest are 0s.
• Subtracting 1 from n flips all the bits after the rightmost 1, including the rightmost 1 itself. For example:
  • n = 8 (1000 in binary), n-1 = 7 (0111 in binary).
  • n & (n-1) will be 0 only when n is a power of two.
• Thus, we return (n > 0) && ((n & (n-1)) == 0).

This method is fast and uses constant space.

Example Walkthrough

Let's walk through the solution with n = 16:

• Check if n > 0: 16 > 0 is true.
• Binary of 16 is 10000.
• n-1 = 15, which is 01111 in binary.
• 16 & 15 = 10000 & 01111 = 00000.
• Since the result is 0, 16 is a power of two.

Now, try n = 12:

• Binary of 12 is 1100.
• n-1 = 11, which is 1011.
• 12 & 11 = 1100 & 1011 = 1000 (not zero).
• So 12 is not a power of two.

Time and Space Complexity

• Brute-force approach: If we checked all powers of two up to n, the time complexity would be O(\log n), since each time we would multiply by 2 until we reach or exceed n.
• Optimized bit manipulation approach: The bitwise operations are constant time, so the time complexity is O(1).
• Space complexity: Both brute-force and optimized approaches use O(1) extra space.

Summary

The key insight is that powers of two have a unique binary pattern: exactly one bit set. By leveraging bit manipulation, we can check this property in constant time using n & (n-1). This approach is much more efficient than looping or recursion and demonstrates the power of understanding binary representations in algorithm design.