326. Power of Three

LeetCode ↗

Problem Editor Pattern Idea Example Code Complex Pitfalls

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

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Math / Bit Manipulation?

This problem maps to Math / Bit Manipulation through a short path in the full flowchart.

Repeatedly divide by three and check that the quotient ends at one with no remainders along the way.

Open in Flowchart

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.

New to patterns?Most interview problems reduce to a handful of patterns. This video covers the main eight.

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:

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.
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.
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.
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³)

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

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

Start with n = 45
Enter loop since 45 > 2
- Check: 45 % 3 = 0 (divisible by 3, continue)
- Divide: n = 45 // 3 = 15
Continue loop since 15 > 2
- Check: 15 % 3 = 0 (divisible by 3, continue)
- Divide: n = 15 // 3 = 5
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

1class Solution:
2    def isPowerOfThree(self, n: int) -> bool:
3        """
4        Determines if a number is a power of three.
5      
6        Args:
7            n: An integer to check if it's a power of 3
8          
9        Returns:
10            True if n is a power of 3, False otherwise
11        """
12        # Keep dividing by 3 while n is greater than 2
13        while n > 2:
14            # If n is not divisible by 3, it's not a power of 3
15            if n % 3 != 0:
16                return False
17            # Divide n by 3 using integer division
18            n //= 3
19      
20        # After the loop, n should be 1 if it was a power of 3
21        # (since 3^0 = 1)
22        return n == 1
23

1class Solution {
2    /**
3     * Determines if a given integer is a power of three.
4     * 
5     * @param n The integer to check
6     * @return true if n is a power of three, false otherwise
7     */
8    public boolean isPowerOfThree(int n) {
9        // Keep dividing by 3 while n is greater than 2
10        while (n > 2) {
11            // If n is not divisible by 3, it cannot be a power of three
12            if (n % 3 != 0) {
13                return false;
14            }
15            // Divide n by 3 to check the next level
16            n /= 3;
17        }
18      
19        // After all divisions, n should be 1 if it was a power of three
20        // (since 3^0 = 1)
21        return n == 1;
22    }
23}
24

1class Solution {
2public:
3    bool isPowerOfThree(int n) {
4        // Keep dividing n by 3 while it's greater than 2
5        while (n > 2) {
6            // If n is not divisible by 3, it's not a power of three
7            if (n % 3 != 0) {
8                return false;
9            }
10            // Divide n by 3 to check the next level
11            n /= 3;
12        }
13      
14        // After the loop, n should be 1 if it was a power of three
15        // (n could be 0, 1, or 2 at this point)
16        // Powers of three: 3^0 = 1, 3^1 = 3, 3^2 = 9, etc.
17        return n == 1;
18    }
19};
20

1/**
2 * Determines if a given number is a power of three
3 * @param n - The number to check
4 * @returns true if n is a power of three, false otherwise
5 */
6function isPowerOfThree(n: number): boolean {
7    // Keep dividing by 3 while n is greater than 2
8    while (n > 2) {
9        // If n is not divisible by 3, it cannot be a power of three
10        if (n % 3 !== 0) {
11            return false;
12        }
13        // Divide n by 3 and continue checking
14        n = Math.floor(n / 3);
15    }
16  
17    // After all divisions, n should be 1 if it was a power of three
18    // (since 3^0 = 1)
19    return n === 1;
20}
21

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.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: