326. Power of Three

Description

The task is to determine whether a given integer n is a power of three. A number is considered a power of three if it can be written as (3^k), where (k) is a non-negative integer.

Intuition

Powers of three grow exponentially, meaning they increase very quickly as the exponent increases. Since there is a limited range of integers that we need to check (from (3^0) to (3^{30}), since (3^{31}) exceeds the maximum value of a typical 32-bit integer), we can iterate through these powers and see if any of them match n.

Approach

1. Iteration through Powers: - Start from (3^0) and calculate powers of 3 incrementally. - For each power, check if it equals n. - If a match is found, return true. If no match is found by the time you reach (3^{30}), return false.
2. Edge Cases: Handle cases where n is less than 1, as negative numbers and zero can never be powers of three.

Complexity

Time Complexity:

• The loop runs up to 31 times (since the largest possible power of three within the 32-bit integer range is (3^{30})).
• Therefore, the time complexity is (O(1)), as it has a constant number of iterations.

Space Complexity:

• We only use a few variables, so the space complexity is (O(1)).

Code

C++

class Solution {
public:
    bool isPowerOfThree(int n) {
        for (int i = 0; i < 31; i++) {
            long long pow = powl(3, i);
            if (pow == n) {
                return true;
            }
        }
        return false;
    }
};

Python

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        for i in range(31):
            if 3 ** i == n:
                return True
        return False

Java

class Solution {
    public boolean isPowerOfThree(int n) {
        for (int i = 0; i < 31; i++) {
            double pow = Math.pow(3, i);
            if (pow == n) {
                return true;
            }
        }
        return false;
    }
}

JavaScript

var isPowerOfThree = function(n) {
    
    for(let i=0;i<31;i++){
        let pow=Math.pow(3,i)
        if(pow===n){
            return true
        }
    }
    return false
};