Difficulty: 🟢 Easy
Topics: Math, Recursion

Solution

LeetCode 326 - Power of Three

Problem Understanding

The problem asks us to determine whether a given integer n can be represented as a power of three. In mathematical terms, we need to check whether there exists an integer x such that:

$$n = 3^x$$

A power of three sequence looks like this:

$$1, 3, 9, 27, 81, 243, \dots$$

The input is a single integer n, and the output should be a boolean value:

Return true if n is exactly equal to some power of three.
Return false otherwise.

An important detail is that powers are only defined for non-negative exponents in this problem context. That means:

3^0 = 1 is considered a valid power of three.
Negative numbers can never be powers of three.
Zero is not a power of three because no exponent satisfies 3^x = 0.

The constraints are:

$$-2^{31} \le n \le 2^{31} - 1$$

This tells us that the input fits within a standard 32-bit signed integer range. Since powers of three grow exponentially, there are only a small number of valid powers of three within this range. Specifically:

$$3^{19} = 1162261467$$

is the largest power of three that fits in a signed 32-bit integer.

Several edge cases are important:

n <= 0 should always return false.
n = 1 should return true because 1 = 3^0.
Large positive numbers that are not exact powers of three should return false.
Negative values should immediately return false.

Approaches

Brute Force Approach

The brute-force idea is straightforward. Starting from n, repeatedly divide by 3 while the number is divisible by 3.

For example:

27 → 9 → 3 → 1

If we eventually reach 1, then the number is a power of three. If at some point the number is not divisible by 3, then it is not a power of three.

This works because every power of three can be reduced to 1 through repeated division by 3.

Although this solution is already efficient enough for the given constraints, it still uses a loop. The follow-up question asks whether we can solve the problem without loops or recursion.

Optimal Mathematical Observation

The key observation is that all powers of three divide the largest power of three within the integer range.

The largest power of three in 32-bit signed integers is:

$$3^{19} = 1162261467$$

If n is a power of three, then it must evenly divide 1162261467.

For example:

1162261467 % 27 == 0
1162261467 % 9 == 0
1162261467 % 12 != 0

This works because powers of three contain no prime factors other than 3. Therefore, every smaller power of three is a divisor of the largest one.

This gives us a constant-time solution without loops or recursion.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(log₃ n)	O(1)	Repeatedly divides by 3 until reaching 1 or failure
Optimal	O(1)	O(1)	Uses divisibility property of the largest 32-bit power of three

Algorithm Walkthrough

Optimal Mathematical Solution

First, check whether n is positive.

Powers of three are always positive numbers. If n <= 0, immediately return false. 2. Store the largest power of three that fits in a 32-bit signed integer.

That value is:

$$1162261467 = 3^{19}$$ 3. Check whether n divides this number evenly.

If:

$$1162261467 \bmod n = 0$$

then n must be a power of three. 4. Return the result of the divisibility check.

Why it works

The number 1162261467 is composed entirely of the prime factor 3. Any divisor of this number must also consist only of the factor 3. Therefore, every positive divisor of 1162261467 is itself a power of three. This guarantees that checking divisibility correctly identifies all powers of three within the 32-bit integer range.

Python Solution

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        MAX_POWER_OF_THREE = 1162261467  # 3^19

        return n > 0 and MAX_POWER_OF_THREE % n == 0

The implementation begins by defining the largest power of three that fits inside a signed 32-bit integer.

The condition n > 0 filters out all invalid values such as zero and negative numbers. This is necessary because modulo operations alone would incorrectly allow negative divisors in some situations.

The second condition checks whether n divides 1162261467 evenly. If it does, then n must be one of the powers of three contained within that number's factorization.

The solution is concise because the mathematical property removes the need for loops or recursion.

Go Solution

func isPowerOfThree(n int) bool {
	const maxPowerOfThree = 1162261467 // 3^19

	return n > 0 && maxPowerOfThree%n == 0
}

The Go implementation follows the same logic as the Python version.

Go uses the % operator for modulo operations just like Python. Since the largest power of three fits comfortably within a 32-bit signed integer, there are no overflow concerns here.

The function directly returns the boolean expression, which keeps the implementation compact and efficient.

Worked Examples

Example 1

Input:

n = 27

Step-by-step evaluation:

Step	Value
Check `n > 0`	`true`
Compute `1162261467 % 27`	`0`
Final Result	`true`

Explanation:

Since 27 divides the maximum power of three evenly, it must itself be a power of three.

Example 2

Input:

n = 0

Step-by-step evaluation:

Step	Value
Check `n > 0`	`false`
Return immediately	`false`

Explanation:

Zero cannot be expressed as 3^x.

Example 3

Input:

n = -1

Step-by-step evaluation:

Step	Value
Check `n > 0`	`false`
Return immediately	`false`

Explanation:

Powers of three are always positive.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a few arithmetic operations are performed
Space	O(1)	No additional data structures are used

The solution performs a constant number of operations regardless of the input size. There are no loops, recursive calls, or auxiliary data structures, so both time and space complexity remain constant.

Test Cases

solution = Solution()

assert solution.isPowerOfThree(27) == True      # standard power of three
assert solution.isPowerOfThree(9) == True       # smaller power of three
assert solution.isPowerOfThree(3) == True       # base case power
assert solution.isPowerOfThree(1) == True       # 3^0

assert solution.isPowerOfThree(0) == False      # zero is not a power
assert solution.isPowerOfThree(-1) == False     # negative number
assert solution.isPowerOfThree(-27) == False    # negative power-like value

assert solution.isPowerOfThree(2) == False      # non-power
assert solution.isPowerOfThree(12) == False     # divisible by 3 but not a pure power
assert solution.isPowerOfThree(45) == False     # composite non-power

assert solution.isPowerOfThree(1162261467) == True   # largest 32-bit power of three
assert solution.isPowerOfThree(1162261466) == False  # just below largest power
assert solution.isPowerOfThree(2147483647) == False  # maximum signed 32-bit integer

Test Case Summary

Test	Why
`27`	Typical valid power of three
`9`	Smaller valid power
`3`	Basic non-trivial power
`1`	Verifies handling of `3^0`
`0`	Confirms zero is rejected
`-1`	Confirms negatives are rejected
`-27`	Negative value resembling a power
`2`	Simple invalid value
`12`	Divisible by 3 but not a power
`45`	Composite number with extra factors
`1162261467`	Largest valid 32-bit power
`1162261466`	Near-boundary invalid value
`2147483647`	Maximum 32-bit integer

Edge Cases

Edge Case 1: Zero

The value 0 is a common source of mistakes because repeated division logic can behave unexpectedly if not handled carefully. No exponent of three produces zero, so the correct answer is always false.

The implementation handles this safely using the condition:

n > 0

This immediately rejects zero before performing the modulo operation.

Edge Case 2: Negative Numbers

Negative integers can never be powers of three because positive bases raised to integer exponents remain positive.

A naive implementation that only checks divisibility might accidentally allow some negative values. The positivity check prevents this issue entirely.

For example:

n = -27

returns false immediately.

Edge Case 3: One

The value 1 is an important mathematical edge case because:

$$1 = 3^0$$

Some implementations incorrectly assume powers must start from 3, causing them to reject 1.

This solution handles it correctly because:

1162261467 % 1 == 0

which returns true.