Power of Four

EASY

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.

Example 1:

Input: n = 16
Output: true

Example 2:

Input: n = 5
Output: false

Example 3:

Input: n = 1
Output: true

Constraints:

-2³¹ <= n <= 2³¹ - 1

Follow up: Could you solve it without loops/recursion?

Approaches

Checkout 4 different approaches to solve Power of Four. Click on different approaches to view the approach and algorithm in detail.

Iterative Approach

This approach uses a loop to check if the given number n is a power of four. We start with a variable, say powerOfFour, initialized to 1. We repeatedly multiply this variable by 4 in a loop. If powerOfFour becomes equal to n at any point, we've found that n is a power of four. If powerOfFour exceeds n, it means n cannot be a power of four, as we've passed the potential value.

Algorithm

Handle the edge case: If n is less than or equal to 0, it cannot be a power of four, so return false.
Initialize a long variable powerOfFour to 1. We use long to prevent overflow when powerOfFour * 4 exceeds Integer.MAX_VALUE.
Start a while loop that continues as long as powerOfFour is less than n.
Inside the loop, update powerOfFour by multiplying it by 4 (powerOfFour *= 4).
After the loop, check if powerOfFour is equal to n. If they are equal, n is a power of four. Otherwise, it is not.

The core idea is to generate powers of four one by one and compare them with the input number n. We start with 4^0 = 1. In each step of a loop, we multiply our current number by 4 to get the next power of four. We stop when our generated number is greater than or equal to the input n. Finally, we check if our number is exactly equal to n.

class Solution {
    public boolean isPowerOfFour(int n) {
        if (n <= 0) {
            return false;
        }
        long powerOfFour = 1;
        while (powerOfFour < n) {
            powerOfFour *= 4;
        }
        return powerOfFour == n;
    }
}

Complexity Analysis

Time Complexity: O(log₄ n). The number of iterations in the loop is proportional to the exponent `x` where `4^x` is close to `n`. This is logarithmic with base 4.Space Complexity: O(1). We only use a few variables to store the state, regardless of the input size.

Pros and Cons

Pros:

Simple to understand and implement.
Works correctly for all valid integer inputs.

Cons:

Less efficient than constant-time solutions.
Does not satisfy the follow-up constraint of solving the problem without loops or recursion.

Code Solutions

Checking out 4 solutions in different languages for Power of Four. Click on different languages to view the code.

class Solution {
public
  boolean isPowerOfFour(int n) {
    return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
  }
}

Video Solution

Watch the video walkthrough for Power of Four

Patterns:

MathRecursionBit Manipulation

Companies:

Qualcomm |Wix |Two Sigma |