Power of Four

Problem Statement

In this task, we are given an integer n and asked to determine whether it is a power of four. Mathematically, an integer is considered a power of four if there exists another integer x such that 4^x = n. This gives rise to a straightforward question: can n be represented as four raised to an integer exponent? The output should be true if n is a power of four and false otherwise.

Examples

Example 1

Input:

n = 16

Output:

true

Example 2

Input:

n = 5

Output:

false

Example 3

Input:

n = 1

Output:

true

Constraints

• -231 <= n <= 231 - 1

Approach and Intuition

To decide whether a number n is a power of four, we can consider the following approach derived from the examples and constraints:

Examples and Intuition

1. Example Analysis:

   • Example 1: n = 16

     • 16 can be expressed as 4^2.
     • Output is true because 16 equals 4 squared.

   • Example 2: n = 5

     • 5 cannot be expressed as 4^x for any integer x.
     • Output is false since no such x makes 4^x = 5.

   • Example 3: n = 1

     • 1 can be expressed as 4^0.
     • Output is true because 1 equals 4 raised to the power of zero.

2. Mathematical Properties:

   • Any number that is a power of four has a binary representation with a single '1' bit at an even position, starting the count from the least significant bit (position 0). This pattern is essential for checking if a number is a power of four using binary manipulations.

3. Use of Constraints:

   • The constraints indicate that n can range from −2^31 to 2^31 - 1, which includes both positive and negative numbers. However, negative numbers and zero cannot be the result of 4^x for any positive integer x, thus quickly excluding all non-positive values.

In the approach, utilize these observations to determine the power status of n efficiently. A common method involves continuous division of n by 4 or using logarithmic properties to check if log4(n) gives an integer. Another possibility, considering performance, is bitwise operations, provided that n is positive and not equal to zero.

Solutions

class Solution {
  public boolean checkIfPowerOfFour(int n) {
    return (n > 0) && ((n & (n - 1)) == 0) && (n % 3 == 1);
  }
}