Skip to main content

Power of Four

Problem 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.

Examples

Example 1:

Input: n = 16
Output: true

Example 2:

Input: n = 5
Output: false

Example 3:

Input: n = 1
Output: true

Constraints

  • -2^31 <= n <= 2^31 - 1

Solution for Power of Four Problem

Approach 1: Brute Force (Loop/Recursion)

The brute force approach involves repeatedly dividing the number by 4 and checking if it becomes 1.

Code in Different Languages

Written by @ImmidiSivani
class Solution {
public:
bool isPowerOfFour(int n) {
if (n < 1) return false;
while (n % 4 == 0) {
n /= 4;
}
return n == 1;
}
};

Complexity Analysis

  • Time Complexity: O(logn)O(\log n), as we keep dividing n by 4.
  • Space Complexity: O(1)O(1), constant space usage.

Approach 2: Optimized (Bit Manipulation)

The optimized approach checks if n is a power of four without loops or recursion. We can use bit manipulation:

  1. n > 0: Ensure n is positive.
  2. n & (n - 1) == 0: Ensure n is a power of two (only one bit set).
  3. (n - 1) % 3 == 0: Ensure n is a power of four (using properties of powers of four).

Code in Different Languages

Written by @ImmidiSivani
class Solution {
public:
bool isPowerOfFour(int n) {
return n > 0 && (n & (n - 1)) == 0 && (n - 1) % 3 == 0;
}
};

Complexity Analysis

  • Time Complexity: O(1)O(1), constant time operations.
  • Space Complexity: O(1)O(1), constant space usage.

Authors:

Loading...