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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Power of Four

Difficulty: Easy

Problem Description

Given an integer n, return true if it is a power of four. Otherwise, return false. An integer n is a power of four if there exists an integer x such that n == 4^x.

Key Insights

  • A number is a power of four if it can be expressed as 4 raised to an integer power.
  • The powers of four can be represented as 1, 4, 16, 64, etc.
  • A number that is a power of four is also a power of two, but it must have an even exponent.
  • We can use mathematical properties or bit manipulation to determine if a number is a power of four without loops or recursion.

Space and Time Complexity

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

Solution

To determine if a number n is a power of four, we can utilize bit manipulation. A number n is a power of four if:

  1. n is greater than 0.
  2. n is a power of two (only one bit is set).
  3. The position of the set bit is even (indicating it is a power of four).

We can check these conditions using bitwise operations:

  • Check if n > 0.
  • Check if n & (n - 1) == 0 (indicating it is a power of two).
  • Check if (n - 1) % 3 == 0 (for powers of four).

Code Solutions

def isPowerOfFour(n: int) -> bool:
    # Check if n is greater than 0 and is a power of two
    return n > 0 and (n & (n - 1)) == 0 and (n - 1) % 3 == 0
← Back to All Questions