Scale Engineer

Power of Four

Easy
#0329Time: 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: O(1). We only use a few variables to store the state, regardless of the input size.3 companies
Patterns
MathRecursionBit Manipulation
Companies
QualcommWixTwo Sigma

Prompt

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 == 4x.

 

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

 

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

Approaches

4 approaches with complexity analysis and trade-offs.

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

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

Walkthrough

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

Time

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

O(1). We only use a few variables to store the state, regardless of the input size.

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem