Power of Two

LeetCode #231 [Easy]

Problem Statement

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: n = 16 ā†’ Output: true (16 = 2^4)
n = 3 ā†’ Output: false

Approach 1: Logarithmic Check

Explanation: Use logarithm base 2 to check if n is a power of two. If log2(n) is an integer, n is a power of two.

Time Complexity: O(1)

Space Complexity: O(1)

if n <= 0:
    return false
x = log2(n)
if x == floor(x):
    return true
else:
    return false

šŸ’” Think: Use log2 and see if the result is an integer, guarding against non-positive n and precision issues.

Approach 2: Iterative Power Check

Explanation: Iterate through possible powers of 2 (up to 2^30) and check if any match n.

Time Complexity: O(log n)

Space Complexity: O(1)

for x in range(0, 31):
    if 2^x == n:
        return true
return false

šŸ’” Think: Generate powers of two up to limits and compare directly with n.

Approach 3: Bit Manipulation

Explanation: A power of two has exactly one bit set in its binary representation. Check if n has only one set bit using bit counting.

Time Complexity: O(1)

Space Complexity: O(1)

if n <= 0:
    return false
return popcount(n) == 1

šŸ’” Think: A power of two has one set bit; check n > 0 and n & (nāˆ’1) == 0.

Solve on LeetCode