Community Problem
Power of Three
Difficulty: Easy
Decide whether a 32-bit signed integer is a power of three using a divisibility shortcut against the largest 32-bit power of three.
Power of Three
Decide whether a 32-bit signed integer is a power of three using a divisibility shortcut against the largest 32-bit power of three.
By @ayomidegray
January 30, 2026
·
Updated May 18, 2026
605 views
11
4.2 (11)
I caught this on a Datadog phone screen right after power-of-two. The follow-up they wanted was the no-loop, no-recursion solution, and the trick is that there is no two-bit identity for base 3. The clean answer leans on a number-theory observation that surprises people the first time they see it.
Power of Three
Given an integer n, return true if it is a power of three. Otherwise, return false.
An integer n is a power of three if there exists an integer x such that n == 3^x.
Examples
Example 1:
- Input:
n = 27 - Output:
true - Explanation:
3^3 == 27.
Example 2:
- Input:
n = 0 - Output:
false - Explanation: There is no integer
xsuch that3^x == 0.
Example 3:
- Input:
n = 9 - Output:
true - Explanation:
3^2 == 9.
Example 4:
- Input:
n = 45 - Output:
false - Explanation:
45 == 3^2 * 5, has a prime factor other than 3.
Example 5:
- Input:
n = 1 - Output:
true - Explanation:
3^0 == 1.
Constraints
-2^31 <= n <= 2^31 - 1.
Follow-up
Could you do it without loops or recursion? Yes, by precomputing the largest 32-bit power of three (3^19 == 1162261467) and checking divisibility, since powers of three are exactly the positive divisors of that number.
Solution
Hints
Solution Walkthrough
Approach: Divisibility Against the Largest 32-bit Power of Three (O(1) time, O(1) space)
Let M = 3^19 = 1162261467 (the largest power of three that fits in a signed 32-bit integer). Because 3 is prime, the positive divisors of M are exactly 3^0, 3^1, ..., 3^19. So a positive integer n <= 2^31 - 1 is a power of three if and only if it divides M evenly.
Key Insight
Why divisibility works
M = 3^19
if n is a power of 3 within range, n = 3^k with k in [0, 19]
3^k divides 3^19 since k <= 19
conversely, if n divides 3^19 and n > 0, n's prime factorization has only 3's,
so n itself is 3^kAlgorithm
- If
n <= 0, returnfalse(powers of three are positive). - Return
(3 ** 19) % n == 0.
Why It Works
The primality of 3 forces every positive divisor of 3^19 to be of the form 3^k. The constraints cap n at 2^31 - 1 < 2 * 3^19, so any n larger than 3^19 cannot be a power of three within range, and the modulus correctly returns non-zero. The n <= 0 guard handles zero and the negative range.
Complexity
Metric Value
Time O(1)
Space O(1)Pitfalls
- Skipping the
n <= 0guard.M % 0is a runtime error in most languages. - Trying the bit-AND trick. Base-3 has no two-operand bit identity; the trick is specific to powers of two.
- Loop-and-divide as a final answer. Acceptable as a backup but the interviewer is usually waiting for the closed-form.
while (n % 3 == 0) n /= 3; return n == 1;works but adds a loop. - Hard-coding the wrong bound.
3^20 = 3486784401overflows signed 32-bit. Use3^19 = 1162261467.
Solution Code