Vultr DocsLatest Content

Power of Four

Updated on 03 July, 2025
Power of Four header image

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

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

This Java solution checks if a given integer n is a power of four. The method checkIfPowerOfFour performs this check using a combination of mathematical and bitwise operations:

  • First, verify if n is positive.
  • Use bitwise AND operation n & (n - 1) to determine if n is a power of two (result should be zero).
  • Confirm that n modulo 3 equals 1, which is a characteristic of all powers of four.

These three conditions ensure the number is not only a power of two but specifically a power of four. This method efficiently filters out numbers that do not meet the precise criteria, returning true only for numbers that are indeed powers of four.

Comments