We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Power of Two

Number: 231

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Meta, Microsoft, Qualcomm, Bloomberg, Apple, Snap, Adobe, Uber, Nvidia

Problem Description

Given an integer n, determine if it is a power of two. In other words, check if there exists an integer x such that n == 2^x. For instance, if n = 16 then return true (since 2^4 = 16) and if n = 3 then return false.

Key Insights

  • A power of two in binary representation contains exactly one set bit.
  • Negative numbers and zero cannot be powers of two.
  • The bit manipulation trick n & (n - 1) can be used to determine if there's exactly one set bit (for n > 0).

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

The algorithm checks whether n is a power of two by leveraging the fact that powers of two have exactly one set bit. First, the check n > 0 ensures the number is positive because only positive numbers can be powers of two. Then, by performing n & (n - 1), we verify that the number has only one set bit. If the result is 0, then n is a power of two; otherwise, it is not. This solution executes in constant time and uses constant space.

Code Solutions

# Function to determine if a number is a power of two
def isPowerOfTwo(n):
    # n must be positive and only one bit should be set in its binary representation.
    return n > 0 and (n & (n - 1)) == 0

# Example usage:
print(isPowerOfTwo(1))  # True, because 2^0 = 1
print(isPowerOfTwo(16)) # True, because 2^4 = 16
print(isPowerOfTwo(3))  # False, 3 is not a power of two
← Back to All Questions