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(log⁡n)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...