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 Four

Number: 342

Difficulty: Easy

Paid? No

Companies: Google, Meta, Apple, Amazon, Adobe, Two Sigma, Wix

Problem Description

Given an integer n, determine whether it is a power of four. In other words, check if there exists an integer x such that n == 4^x. The solution should be achieved without using loops or recursion.

Key Insights

  • n must be positive because powers of four are positive.
  • A power of four is also a power of two (only one bit is set in its binary representation).
  • The single 1 in the binary representation must be in the correct position; that is, it should be in an odd-numbered bit position (starting from bit 0).
  • Use bit manipulation to check if n is a power of two and then use a mask (0x55555555) to ensure the single bit is in the correct position.

Space and Time Complexity

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

Solution

The solution first checks if n is positive. Then, using the bit manipulation trick, it verifies that only one bit is set by ensuring n & (n-1) equals zero (a standard check for powers of two). After that, a bit mask is applied to confirm that the one bit is positioned correctly within the binary representation for a power of four. The mask 0x55555555 (in hexadecimal) has bits set in positions 0, 2, 4, etc. If the result of n & 0x55555555 is non-zero along with the previous conditions, then n is a power of four.

Code Solutions

# Function to check if n is a power of four
def isPowerOfFour(n):
    # n must be positive
    if n <= 0:
        return False
    # Check if there is only one bit set (power of two) 
    # and the bit is positioned correctly (using the mask 0x55555555).
    return (n & (n - 1)) == 0 and (n & 0x55555555) != 0

# Example usage:
print(isPowerOfFour(16))  # Should print True
print(isPowerOfFour(5))   # Should print False
print(isPowerOfFour(1))   # Should print True
← Back to All Questions