Abstract / Summary

Given an integer, determine if it is a power of three.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 51% (2+ million submissions).

Typical patterns to solve this problem:

• Math
• Recursion

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation determines whether a given integer n is an exact power of three. It follows a straightforward enumeration strategy: generate successive powers of three, compare each with the target value, and stop as soon as the generated power either matches the target or exceeds it. The algorithm also includes a special-case guard for the value zero.

Key Steps

Guard for Zero

if n == 0:
    return False

The function immediately rejects zero because zero cannot be expressed as (3^k) for any integer exponent (k). This early exit prevents unnecessary computation for the most common non-positive input.

Bounded Enumeration Loop

for i in range(21):  # 3^21 > 2^32
    triple = 3**i
    if triple == n:
        return True
    if triple > n:
        break

The loop iterates over a fixed range of exponents from 0 up to 20 inclusive. The comment explains that the upper bound is chosen because (3^{21}) already exceeds the maximum value representable by a 32-bit unsigned integer, guaranteeing that any valid power of three fitting in a typical integer range will be encountered before the loop terminates.

Inside the loop, the current power of three is computed with the exponentiation operator. Two conditional checks follow:

• If the generated power equals n, the function returns True immediately, confirming that n is a power of three.
• If the generated power surpasses n, the loop breaks because further powers will only grow larger, making a match impossible.

Default Return

return False

If the loop completes without finding a match, the function concludes that n is not a power of three and returns False.

Edge Cases Handled

The code gracefully handles several boundary conditions:

• Zero Input - The explicit guard returns False without entering the enumeration loop.
• Negative Numbers - For any negative n, the first generated power (3**0 equals 1) is already greater than n. The if triple > n: condition triggers on the first iteration, causing an immediate break and a final False return.
• One as Input - Since 3**0 equals 1, the equality check succeeds on the first loop iteration, resulting in a True return. This correctly identifies 1 as (3^0).
• Values Larger Than the Largest 32-bit Power of Three - The loop’s upper bound of 21 ensures that any integer exceeding the range of representable powers of three will cause the loop to terminate after the last iteration, ultimately returning False.

Performance Optimizations

The implementation incorporates several techniques that reduce unnecessary work:

• Early Exit for Zero - By handling the zero case up front, the function avoids the overhead of the loop for an input that can be decided instantly.
• Fixed Upper Bound - Limiting the loop to 21 iterations eliminates the risk of an unbounded search and ensures a predictable execution ceiling regardless of the input size.
• Break on Exceeding Target - As soon as a generated power surpasses n, the loop stops. This prevents the function from continuing to compute larger powers that could never match the target, especially beneficial when n is far smaller than the maximum bound.
• Immediate Return on Match - Detecting an exact match triggers an instant return, avoiding any further iteration once the answer is known.

These choices collectively keep the runtime short and the memory footprint minimal, making the function well-suited for environments where deterministic performance is important.

Imagine you have a magical growing machine that only knows how to multiply things by three. It starts with one, then it turns that into three, then it turns that three into nine, and keeps going like that by multiplying by three over and over again.

This code is like a little detective looking at a mystery number called n. The detective wants to know if the number n came from that magical growing machine. To find out, it has a checklist for the first twenty-one steps of the machine. It starts at the very beginning and calculates what the machine would have produced at each step. If the number on the list matches the mystery number n exactly, then the detective knows the secret is solved. If the machine grows past the mystery number and still has not matched it, the detective stops looking because it knows the number will never appear.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		JS	Go	Rust		TS
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python								TS
	Progiez	C++	Python		Java
github	BigEggStudy			C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai				Java
	DimitrisJim					C
	everthis						JS
	fartem									Ruby
	FelixFan1122			C#
	fpdjsns	C++
	Garvit244		Python
	halfrost							Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	Krazune					C
	linouk23	C++
	lkwq007		Python
	muhammadfarhankt							Go
	pruthvikp		Python
	qiyuangong		Python
	ruoru								Rust
	shreymehul			C#
	sonugiri1043	C++
	suxrobGM			C#
	varunu28				Java
	vli02					C
	vthwang				Java
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fpdjsns	C++
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C
linouk23	C++
lkwq007	Python
muhammadfarhankt	Go
pruthvikp	Python
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality