326. Power of Three

On LeetCode ->

Reformulated question¶

Given an integer n, return whether it is exactly some power of 3, meaning \(n = 3^k\) for an integer \(k \ge 0\).

Example: n=27 -> True because 27 = 3^3

Key trick¶

Use the integer limit.

In 32-bit signed range, the largest power of 3 is 3^19 = 1162261467.
A positive n is a power of 3 iff it divides that number exactly.

Trap¶

Forgetting that 1 is a power of 3 because \(1 = 3^0\).
Accepting 0 or negatives.
Using logs, which can fail from floating-point precision.
Misreading the statement as n == 3*x instead of n == 3^x.

Why this question is interesting¶

It looks trivial, but it tests whether you notice a math shortcut instead of defaulting to recursion or floating-point hacks.

Solve the problem with idiomatic Python¶

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        # 3^19 is the largest power of 3 in 32-bit signed integer range.
        # If n is a positive power of 3, it must divide 3^19.
        return n > 0 and 1162261467 % n == 0

class SolutionLoop:
    def isPowerOfThree(self, n: int) -> bool:
        # Simple direct approach: keep dividing by 3.
        while n > 0 and n % 3 == 0:
            n //= 3
        return n == 1

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("n", "expected"),
    [
        (1, True),
        (3, True),
        (9, True),
        (27, True),
        (243, True),
        (1162261467, True),   # 3^19, largest power of 3 in 32-bit signed int
        (0, False),
        (-1, False),
        (-3, False),
        (2, False),
        (45, False),
        (1162261466, False),
    ],
)
def test_is_power_of_three(n, expected):
    assert Solution().isPowerOfThree(n) is expected

Comment my solution¶

Your recursive solution is correct.

Good:
- Handles n <= 0.
- Correctly treats 1 as a power of 3.
- Uses integer arithmetic only.
Small issue:
- Recursion is fine here, but iterative or divisibility-by-3^19 is shorter.
- For the follow-up, recursion does not satisfy "without loops/recursion".
About the commented log solution:
- Correct to reject it.
- Floating-point logs are unreliable for exact integer-power checks.

import pytest
from math import log

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

# WRONG: log is not precise.
# log(243, 3) # 4.999999999999999
#
# class SolutionNoRecursion:
#     def isPowerOfThree(self, n: int) -> bool:
#         if n <= 0:
#             return False
#         k = int(log(n, 3))
#         return n == 3**k

# log(27, 3) # 3.0
# log(3**6, 3)  # 6.0
# log(243, 3) # 4.999999999999999

@pytest.mark.parametrize(
    ("n", "is_power_of_three"),
    [
        (27, True),
        (53, False),
        (243, True),
        (-27, False),
        (1, True),
        (0, False),
        (-1, False),
        (-3, False)
    ]
)
def test_isPowerOfThree(n, is_power_of_three):
    assert Solution().isPowerOfThree(n) == is_power_of_three

# k = 1
# while 3**k < (2**31 - 1):
#     k += 1
# k - 1 # 19
# 3**19 # 1162261467