Code Implementation

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        while n % 3 == 0:
            n //= 3
        return n == 1
      

class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n <= 0) return false;
        while (n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
};
      

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) return false;
        while (n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}
      

var isPowerOfThree = function(n) {
    if (n <= 0) return false;
    while (n % 3 === 0) {
        n = n / 3;
    }
    return n === 1;
};
      

Problem Description

Given an integer n, determine whether it is a power of three. In other words, return true if there exists an integer k such that n == 3k, where k is an integer and k ≥ 0. Otherwise, return false.

• Input: A single integer n.
• Output: true if n is a power of three, false otherwise.
• Constraints: The solution should not use loops or recursion for some follow-up versions, but for this base version, loops are allowed.

Thought Process

To determine if a number is a power of three, we need to check if it can be expressed as 3k for some integer k (where k ≥ 0). The most straightforward approach is to keep dividing the number by 3 as long as it is divisible by 3. If we eventually reach 1, then the original number was a power of three. If not, it was not.

Initially, one might think to try all powers of three and check if any match n. However, this is unnecessary; instead, it's more efficient to continuously divide n by 3 and check the remainder. This avoids unnecessary calculations and directly tests the property that defines powers of three.

Solution Approach

• Step 1: Check if n is less than or equal to zero. If so, return false immediately, because powers of three are always positive.
• Step 2: While n is divisible by 3 (i.e., n % 3 == 0), divide n by 3.
• Step 3: After the loop, check if n has been reduced to 1. If yes, n was a power of three; otherwise, it was not.

This approach is efficient because each division by 3 reduces the size of n quickly, and the number of operations is proportional to the logarithm of n base 3.

Example Walkthrough

Let's take n = 27 as an example:

• Start with n = 27. Is 27 divisible by 3? Yes. Divide: 27 / 3 = 9.
• Now n = 9. Is 9 divisible by 3? Yes. Divide: 9 / 3 = 3.
• Now n = 3. Is 3 divisible by 3? Yes. Divide: 3 / 3 = 1.
• Now n = 1. We stop. Since we reached 1, the original number 27 is a power of three (specifically, 3³).

For a non-power-of-three (e.g., n = 10):

• 10 is divisible by 3? No. The loop does not run, and since 10 ≠ 1, we return false.

Time and Space Complexity

• Brute-force approach: If we tried to generate all powers of three up to n, the time complexity would still be O(log₃n), but with more overhead.
• Optimized approach (current): Each division by 3 reduces n by a factor of 3, so the loop runs at most log₃n times. Thus, the time complexity is O(log n).
• Space complexity: No extra space is used beyond a constant number of variables. Thus, the space complexity is O(1).

Summary

The problem asks us to determine if a number is a power of three. By repeatedly dividing the number by 3 and checking if we end up with 1, we can efficiently solve the problem in logarithmic time and constant space. This approach is simple, direct, and leverages the mathematical definition of powers of three for a clean and elegant solution.