File: power-of-three/solution.py

Date: 2026-06-06

Time: 18:34

power-of-three/solution.py

Purpose

This file solves LeetCode 326 — Power of Three. It determines whether a given integer is a power of three (i.e., 3^0, 3^1, 3^2, ...). It's one of hundreds of self-contained solution modules in the leetcode-implementations repo, each owning exactly one problem.

Key Components

ispowerof_three(n: int) -> bool — The sole function. It uses a constant-time, loop-free approach based on a number-theoretic trick rather than the naive "keep dividing by 3" strategy.

The magic constant 1162261467 is 3^19, the largest power of 3 that fits in a 32-bit signed integer (max 2^31 - 1 = 2,147,483,647). Because 3 is prime, the only divisors of 3^19 are 3^0, 3^1, ..., 3^19. So 1162261467 % n == 0 is true if and only if n is a power of three.

The n > 0 guard rejects zero and negatives — no negative integer or zero is a power of three, and % 0 would be a ZeroDivisionError.

Patterns

• Mathematical shortcut over iteration: Instead of a loop (while n % 3 == 0: n //= 3) which is O(log n), this is O(1) time and space. The tradeoff is readability — the magic number requires the docstring to make sense.
• Problem-scoped constraint exploitation: The solution assumes 32-bit signed integer range, which is the constraint LeetCode specifies. If n could exceed 2^31, this approach breaks — you'd need a larger maximal power of 3.

Dependencies

Imports: None. Pure arithmetic, no standard library needed.

Imported by: The power-of-three/testsolution.py file imports this function directly. The massive "Imported By" list in the prompt is misleading — those are unrelated test files that likely share a common test harness import pattern, not actual consumers of ispowerofthree.

Flow

1. Caller passes an integer n.

2. Check n > 0 — short-circuits to False for non-positive inputs.

3. Compute 1162261467 % n — if the remainder is 0, n divides 3^19, meaning n is itself a power of 3.

4. Return the boolean result.

Invariants

• Domain constraint: Only valid for inputs in the 32-bit signed integer range. For larger inputs, 3^19 is no longer the correct ceiling.
• Primality dependency: The trick works because 3 is prime. For composite bases (e.g., "power of 6"), the largest power of the base would have divisors that aren't themselves powers of the base, and this approach would produce false positives.

Error Handling

None needed. The n > 0 guard prevents the only runtime error (ZeroDivisionError when n == 0). All other inputs produce a valid boolean. No exceptions are raised or caught.