🗼Beginners guide to "Leetcode 231: Power of Two"(C++ | JavaScript | Python)

#programming #cpp #javascript #python

The task is simple: determine whether a given integer n is a power of two. In other words, return true if there exists some integer x such that:

n == 2^x

Otherwise, return false.

Intuition

A power of two always has exactly one bit set in its binary representation. For example:

1 = 2^0 → 0b0001
2 = 2^1 → 0b0010
4 = 2^2 → 0b0100
8 = 2^3 → 0b1000

All of these have exactly one bit set to 1. Any number that is not a power of two will either have multiple bits set or will be less than or equal to 0.

This leads to an efficient bitwise approach to check whether n is a power of two without using loops or recursion.

Approach

We use the __builtin_popcount(n) function available in GCC/Clang-based compilers. This function returns the number of set bits (bits equal to 1) in the binary representation of n.

A power of two has exactly one set bit, so we check if __builtin_popcount(n) == 1.
We also ensure n > 0, since negative numbers and zero cannot be powers of two.

C++ Code

class Solution {
 public:
  bool isPowerOfTwo(int n) {
    return n > 0 && __builtin_popcount(n) == 1;
  }
};

JavaScript Version

JavaScript does not have a built-in popcount function, but we can convert the number to binary and count the number of 1s:

var isPowerOfTwo = function(n) {
    return n > 0 && n.toString(2).split('1').length - 1 === 1;
};

Alternatively, use a bitwise trick:

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

Python Version

Python also lacks a direct popcount, but we can use the bin() function:

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and bin(n).count('1') == 1

Or using the bitwise trick:

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

Time and Space Complexity

Time Complexity: O(1)
All operations—whether counting bits or doing bitwise checks—are constant time.
Space Complexity: O(1)
No extra memory is used.

Final Thoughts

This is a straightforward bit manipulation problem. The use of __builtin_popcount or (n & (n - 1)) == 0 makes the check both efficient and concise. Knowing how powers of two behave in binary is the key insight here.