algoadvance

Given an integer n, write a function to determine if it is a power of two. A power of two is a number of the form (2^x) where x is an integer.

Clarifying Questions:

  1. Input Range: Are there any constraints on the input range for n?
    • Generally, n will be a 32-bit signed integer, so it can range from -2,147,483,648 to 2,147,483,647.
  2. Edge Cases:
    • Should the function return False for non-positive numbers (0 and negative numbers)?
      • Yes, only positive powers of two are to be considered, so non-positive numbers should return False.
  3. Efficiency:
    • Does it need to be done in constant time?
      • A logarithmic or constant time solution is preferable.

Strategy:

  1. Positive Check:
    • First, we need to check whether n is positive. If it isn’t, we should return False.
  2. Bit Manipulation:
    • The most efficient way to check if a number is a power of two is through bit manipulation.
    • A power of two has exactly one bit set in its binary representation.
    • This property allows us to use the condition (n & (n - 1)) == 0 to check for powers of two. This works because:
      • (n - 1) flips all bits after the rightmost set bit (including the set bit itself).
      • Performing an AND operation between n and (n - 1) should result in 0 if n is a power of two.
  3. Edge Cases Handling:
    • If n <= 0, immediately return False.

Code:

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

# Test cases
print(isPowerOfTwo(1))   # True (2^0)
print(isPowerOfTwo(16))  # True (2^4)
print(isPowerOfTwo(218)) # False
print(isPowerOfTwo(1024))# True (2^10)
print(isPowerOfTwo(0))   # False
print(isPowerOfTwo(-4))  # False

Time Complexity:

This method is efficient and covers all edge cases as required.

Try our interview co-pilot at AlgoAdvance.com