Problem Description

Given an integer n, you need to determine if it is a power of three. Return true if n is a power of three, otherwise return false.

A number n is considered a power of three if there exists some integer x such that n == 3^x. In other words, n can be expressed as 3 multiplied by itself x times.

For example:

• n = 27 returns true because 27 = 3^3
• n = 9 returns true because 9 = 3^2
• n = 45 returns false because 45 cannot be expressed as 3^x for any integer x

The solution uses trial division to check if n is a power of three. It repeatedly divides n by 3 as long as n is greater than 2 and divisible by 3. If at any point n is not divisible by 3 (when n % 3 is non-zero), the function returns false. After the loop ends, if n equals 1, it means the original number was a power of three, so the function returns true. Otherwise, it returns false.

Intuition

To check if a number is a power of three, we need to think about what it means mathematically. If n = 3^x, then we can keep dividing n by 3 exactly x times until we reach 1. This is the key insight.

Think of it like peeling layers off an onion. If we have 27 = 3^3, we can divide by 3 three times: 27 ÷ 3 = 9, then 9 ÷ 3 = 3, then 3 ÷ 3 = 1. We end up with exactly 1, confirming that 27 is indeed a power of three.

On the other hand, if we try this with a non-power like 45: 45 ÷ 3 = 15, then 15 ÷ 3 = 5. Now 5 is not divisible by 3 (it gives remainder 2), so we know 45 cannot be a power of three.

The pattern becomes clear: a power of three should be repeatedly divisible by 3 until we reach 1, with no remainders along the way. If at any point during our division we get a remainder (checked using n % 3), we immediately know the number isn't a power of three.

The algorithm naturally emerges from this observation: keep dividing by 3 while checking for remainders. If we successfully reduce the number to 1 through repeated division by 3, it's a power of three. If we encounter a remainder or end up with a number other than 1, it's not.

Solution Approach

The solution implements the trial division method to determine if a number is a power of three. Let's walk through the implementation step by step:

1. Main Loop Condition: The algorithm starts with a while loop that continues as long as n > 2. This is because the smallest power of three greater than 2 is 3^1 = 3. Any power of three will be at least 3, so we can stop when n becomes 2 or less.

2. Divisibility Check: Inside the loop, we check if n % 3 is non-zero. The modulo operation n % 3 returns the remainder when n is divided by 3. If there's any remainder (meaning n % 3 evaluates to true), then n is not perfectly divisible by 3, which means it cannot be a power of three. We immediately return False.

3. Division Step: If n is divisible by 3 (passes the modulo check), we perform integer division: n //= 3. This reduces n by a factor of 3 and continues the process. The integer division operator // ensures we're working with whole numbers throughout.

4. Final Check: After the loop exits (when n <= 2), we check if n == 1. If we've successfully divided a power of three by 3 repeatedly, we should end up with exactly 1. For example:

   • 27 → 9 → 3 → 1 (returns True)
   • 18 → 6 → 2 (returns False since 2 ≠ 1)

The algorithm has a time complexity of O(log n) because we're dividing n by 3 in each iteration, which means the number of iterations is proportional to log₃(n). The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's trace through the algorithm with two examples to see how it works:

Example 1: n = 27 (which is 3³)

1. Start with n = 27
2. Enter loop since 27 > 2
   • Check: 27 % 3 = 0 (divisible by 3, continue)
   • Divide: n = 27 // 3 = 9
3. Continue loop since 9 > 2
   • Check: 9 % 3 = 0 (divisible by 3, continue)
   • Divide: n = 9 // 3 = 3
4. Continue loop since 3 > 2
   • Check: 3 % 3 = 0 (divisible by 3, continue)
   • Divide: n = 3 // 3 = 1
5. Exit loop since 1 ≤ 2
6. Final check: n == 1? Yes! Return true

Example 2: n = 45 (not a power of three)

1. Start with n = 45
2. Enter loop since 45 > 2
   • Check: 45 % 3 = 0 (divisible by 3, continue)
   • Divide: n = 45 // 3 = 15
3. Continue loop since 15 > 2
   • Check: 15 % 3 = 0 (divisible by 3, continue)
   • Divide: n = 15 // 3 = 5
4. Continue loop since 5 > 2
   • Check: 5 % 3 = 2 (not divisible by 3!)
   • Return false immediately

The algorithm efficiently identifies that 27 can be reduced to 1 through repeated division by 3, while 45 fails the divisibility test when we reach 5, proving it's not a power of three.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log₃n)

The algorithm uses a while loop that repeatedly divides n by 3 until n becomes less than or equal to 2. In each iteration, we perform:

• A modulo operation n % 3 to check divisibility
• An integer division n //= 3 to reduce n

The number of iterations is determined by how many times we can divide n by 3 before it becomes less than or equal to 2. This is equivalent to finding the largest integer k such that 3^k ≤ n, which gives us k ≤ log₃n. Therefore, the loop runs at most ⌊log₃n⌋ times, resulting in a time complexity of O(log₃n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• The input variable n is modified in place
• No additional data structures are created
• The space used does not depend on the size of the input

Therefore, the space complexity is O(1).

Common Pitfalls

Pitfall 1: Not Handling Non-Positive Numbers

The current implementation fails for non-positive integers (0 and negative numbers). Since powers of three are always positive (3^x > 0 for any real x), the function should immediately return False for any n ≤ 0. However, the current code will:

• For n = 0: The while loop doesn't execute (0 < 2), and 0 == 1 returns False (correct by accident)
• For n = -27: The while loop doesn't execute (-27 < 2), and -27 == 1 returns False (correct by accident)
• For n = 1: The while loop doesn't execute (1 < 2), and 1 == 1 returns True (correct, since 3^0 = 1)

Solution: Add an explicit check at the beginning:

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

Pitfall 2: Loop Condition Edge Case

The condition n > 2 might seem arbitrary and could be confusing. A cleaner approach would be to continue dividing while n is divisible by 3 and greater than 1:

Alternative Solution:

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

This version is more intuitive: keep dividing by 3 as long as possible, then check if we're left with 1.

Pitfall 3: Integer Overflow in Other Languages

While Python handles arbitrarily large integers, in languages like Java or C++, there's a mathematical trick that avoids loops entirely. The largest power of 3 that fits in a 32-bit signed integer is 3^19 = 1162261467. If n is a power of 3, it must divide this number evenly:

Mathematical Solution (for languages with fixed integer sizes):

def isPowerOfThree(self, n: int) -> bool:
    # 3^19 is the largest power of 3 in 32-bit range
    return n > 0 and 1162261467 % n == 0

This approach has O(1) time complexity but relies on the constraint that n fits within a specific integer range.