Problem Statement in English

You are given an integer n. Your task is to determine if n is a power of two. Further, they ask us to not use loops or recursion in our solution.

Approach

To determine if a number n is a power of two, we can use the property that a power of two has exactly one bit set in its binary representation.

Thus, all we need to do is find the most significant bit (MSB) of n and check if 2^msb equals n.

Solution in Python


class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        msb = len(bin(n)[2:]) - 1
        return pow(2, msb) == n

Complexity

  • Time: $O(1)$
    Since we are only performing a constant number of operations to determine the most significant bit and check if n is a power of two, the time complexity is $O(1)$.

  • Space: $O(1)$
    Since we use a constant amount of space for the variable msb, the space complexity is $O(1)$.

And we are done.