algoadvance

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.

Clarifying Questions

  1. Input Range: Are there any constraints on the input value n?
    • Assumption: The input n is a 32-bit signed integer.
  2. Edge Cases: How should the function handle the edge cases such as n = 0 or n = 1?
    • Assumption: n = 0 should return false, and n = 1 should return true since 4^0 = 1.

Strategy

  1. Initial Check: If n is less than or equal to zero, it cannot be a power of four. Return false.

  2. Pattern Matching: Using logarithms. A number n is a power of four if log4(n) is an integer. We can use the change of base formula:
    • log4(n) = log(n) / log(4)
    • If the result is an integer, then n is a power of four.
  3. Bit Manipulation: This approach uses bit manipulation properties specific to powers of four:
    • Power of four numbers in binary form are 1 followed by an even number of 0s. This property makes the bitwise AND operation useful.
    • The number must be a power of two (i.e., n & (n - 1) == 0).
    • The number mod 3 should be 1 (since 4^x % 3 = 1).

Here, we’ll go with the bit manipulation approach as it is more efficient in terms of time complexity.

Code

def isPowerOfFour(n: int) -> bool:
    if n <= 0:
        return False
    return (n & (n - 1)) == 0 and (n % 3 == 1)

Explanation

  1. Check negativity and zero: If n is non-positive (n <= 0), return false.
  2. Power of Two Check: (n & (n - 1)) == 0 checks if n is a power of two.
  3. Power of Four Check: (n % 3 == 1) ensures n is specifically a power of four by checking its modulo 3.

Time Complexity

The time complexity of this approach is O(1) because all the operations involved (bitwise AND, comparison, and modulo) are constant time operations.

Try our interview co-pilot at AlgoAdvance.com