LeetCode 326: Power of Three Solution in Python – A Step-by-Step Guide

What Is LeetCode 326: Power of Three?

In LeetCode 326: Power of Three, you’re given an integer n, and your task is to determine if it’s a power of 3 (i.e., n = 3^k for some integer k ≥ 0). For example, 27 is (3³), but 45 isn’t. This problem tests your ability to recognize mathematical patterns, connecting to number theory concepts like those in LeetCode 231: Power of Two.

Problem Statement

• Input: An integer n.
• Output: A boolean—True if n is a power of 3, False otherwise.
• Rules:
• n is a power of 3 if n = 3^k for some integer k ≥ 0.
• No loops or recursion allowed in the optimal solution (though we’ll explore both).

Constraints

• -2³¹ <= n <= 2³¹ - 1

Examples

• Input: 27
• Output: True (27 = 3³)
• Input: 0
• Output: False (No power of 3)
• Input: 45
• Output: False (Not a power of 3)

Understanding the Problem: Spotting Powers of Three

To solve LeetCode 326: Power of Three in Python, we need to check if n can be expressed as 3^k. A naive approach—dividing by 3 repeatedly—works but takes O(log n) time. We can do better with math! We’ll use:

• Best Solution (Math Trick): O(1) time, O(1) space—pure brilliance.
• Alternative Solution (Iterative): O(log n) time, O(1) space—simple and clear.

Let’s start with the math trick solution, explained in a beginner-friendly way.

Best Solution: Math Trick (Largest Power Check)

Why This Is the Best Solution

The math trick approach is the top choice for LeetCode 326 because it’s constant-time—O(1) time, O(1) space—and avoids loops or recursion entirely. It uses a clever property: if n is a power of 3, it must divide the largest power of 3 within the 32-bit integer range (3¹⁹ = 1,162,261,467). It’s like checking a secret password—fast and elegant!

How It Works

Think of this as a master key test:

• Step 1: Define Largest Power:
• Max 32-bit int = 2³¹ - 1 ≈ 2.14 * 10⁹.
• Largest 3^k ≤ 2³¹ - 1 is 3¹⁹ = 1,162,261,467.
• Step 2: Check Divisibility:
• If n is a power of 3, then 3¹⁹ % n == 0 (n divides 3¹⁹).
• Also, n > 0 (since powers of 3 are positive).
• Step 3: Why It Works:
• Every power of 3 (3⁰, 3¹, ..., 3¹⁹) divides 3¹⁹ evenly.
• Non-powers (e.g., 6) don’t, leaving a remainder.

It’s like a math shortcut to the answer!

Step-by-Step Example

Example: n = 9

• Largest Power: 3¹⁹ = 1,162,261,467
• Check:
• n > 0: True (9 > 0)
• 3¹⁹ % 9 = 1,162,261,467 % 9 = 0 (since 9 = 3² divides 3¹⁹)
• Result: True (9 is 3²)

Example: n = 45

• Check:
• 3¹⁹ % 45 ≈ 25,828,032 (remainder ≠ 0)
• Result: False

Code with Detailed Line-by-Line Explanation

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

• Line 3: Single line check:
• n > 0: Powers of 3 are positive.
• 1162261467 % n == 0: n must divide 3¹⁹.
• Time Complexity: O(1)—constant-time modulo.
• Space Complexity: O(1)—no extra space.

This is like a math-powered lightning bolt—instant and sleek!

Alternative Solution: Iterative Division

Why an Alternative Approach?

The iterative approach—O(log n) time, O(1) space—divides n by 3 repeatedly until it’s 1 or not divisible, offering a hands-on way to see if it’s a power of 3. It’s simpler to understand but slower, making it a great learning tool. It’s like peeling layers to check the core—straightforward and tangible!

How It Works

Divide and conquer:

• Step 1: Handle edge cases (n ≤ 0).
• Step 2: While n > 1:
• If n % 3 ≠ 0, return False.
• Divide n by 3.
• Step 3: Check if n = 1 (a power of 3).

Step-by-Step Example

Example: n = 27

• Divide: 27 / 3 = 9
• Divide: 9 / 3 = 3
• Divide: 3 / 3 = 1
• Result: True (27 = 3³)

Example: n = 12

• Divide: 12 % 3 = 0, 12 / 3 = 4
• Divide: 4 % 3 ≠ 0
• Result: False

Code for Iterative Approach

Copy codeclass Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False

        while n > 1:
            if n % 3 != 0:
                return False
            n //= 3

        return n == 1

• Time Complexity: O(log n)—number of divisions.
• Space Complexity: O(1)—just n.

It’s a step-by-step power checker—clear and steady!

Comparing the Two Solutions

• Math Trick (Best):
• Pros: O(1) time, O(1) space, no loops.
• Cons: Requires math insight.
• Iterative (Alternative):
• Pros: O(log n) time, O(1) space, easy to follow.
• Cons: Slower for large n.

Math trick wins for speed.

Additional Examples and Edge Cases

• 1: True (3⁰).
• -3: False (negative).
• 0: False (not a power).

Both handle these perfectly.

Complexity Breakdown

• Math Trick: Time O(1), Space O(1).
• Iterative: Time O(log n), Space O(1).

Math trick is the clear champ.

Key Takeaways

• Math Trick: Clever constant—fast!
• Iterative: Divide and check—simple!
• Python: Math ops shine—see [Python Basics](/python/basics).
• Powers: Patterns unlock answers.

Final Thoughts: Spot the Power

LeetCode 326: Power of Three in Python is a math-meets-coding gem. The math trick solution offers instant elegance, while iteration provides a tangible process. Want more number challenges? Try LeetCode 231: Power of Two or LeetCode 342: Power of Four. Ready to check? Head to Solve LeetCode 326 on LeetCode and power up your skills today!