SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem asks to determine if a given integer n is a power of four. A number is considered a power of four if it can be expressed as 4^k where k is a non-negative integer.

Intuition

The key observation is that powers of four follow a specific pattern where n is divisible by 4 until the result becomes 1. For example, 4^0 = 1, 4^1 = 4, 4^2 = 16, and so on. Hence, if a number is divisible by 4 and repeatedly dividing it by 4 eventually gives 1, the number is a power of four.

Approach

The approach uses recursion to divide the number by 4 at each step:

1. If n equals 1, return true since 4^0 = 1 is a valid power of four.
2. If n is less than or equal to zero or not divisible by 4, return false because it can't be a power of four.
3. Recursively divide n by 4 and check if the result is a power of four.

Complexity

Time Complexity:

O(log n) - The number n is repeatedly divided by 4, so the number of operations grows logarithmically relative to n.

Space Complexity:

O(log n) - Due to the recursive calls, the space used on the call stack grows with the number of divisions.

Code

C++

class Solution {
public:
    bool isPowerOfFour(int n) {
        if (n == 1) return true;
        if (n <= 0 || n % 4 != 0) return false;
        return isPowerOfFour(n / 4);
    }
};

Python

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n == 1:
            return True
        if n <= 0 or n % 4 != 0:
            return False
        return self.isPowerOfFour(n // 4)

Java

class Solution {
    public boolean isPowerOfFour(int n) {
        if (n == 1) return true;
        if (n <= 0 || n % 4 != 0) return false;
        return isPowerOfFour(n / 4);
    }
}

JavaScript

var isPowerOfFour = function (n) {

    if (n == 1) return true;
    if (n <= 0 || n % 4 != 0) return false;
    
    return isPowerOfFour(n / 4);
};