Power of Three — Solution in Python, Java & C++
Power of Three solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on math and recursion.
Power of Three is an easy coding problem on math and recursion, asked in Amazon, Google and Hulu interviews.
- Difficulty: Easy
- Topics: Math, Recursion
- Asked at: Amazon, Google, Hulu
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer n, return true if it is a power of three — that is, if there exists an integer x with n == 3^x.
Example 1
Input: n = 27
Output: true
Explanation: 3^3 = 27.
Example 2
Input: n = 0
Output: false
Example 3
Input: n = 45
Output: false
Explanation: 45 = 3² × 5.
Constraints
-2^31 <= n <= 2^31 - 1
Follow-up: Can you solve it without loops or recursion?
Hints for Power of Three
Hint 1
The loop solution divides by 3 while the remainder is zero and checks that 1 is left.
Hint 2
Three is prime, so the only divisors of 3^19 that are themselves powers of three are 3^0 … 3^19.
Hint 3
3^19 = 1162261467 is the largest power of three inside a 32-bit int — test whether it is divisible by
n.
How to solve Power of Three
Three is prime, so every divisor of 3^19 — the largest power of three that fits in a 32-bit int — is itself a power of three. Test whether 1162261467 % n == 0.
Approach
- Return
falseforn <= 0. - Return
1162261467 % n == 0.
Why it works
By unique factorisation the divisors of 3^19 are exactly 3^0, 3^1, …, 3^19. Every positive power of three within int range is in that list, and any number with another prime factor cannot divide 3^19.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- This trick works only because 3 is prime —
4^kdivides4^15but so does2. - Dividing by 3 in a loop while the remainder is zero and checking for
1is the portable version if you cannot remember the constant.
Reference solution
Python
def isPowerOfThree(n: int) -> bool:
return n > 0 and 1162261467 % n == 0Java
public static boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}C++
bool isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}JavaScript
var isPowerOfThree = function(n) {
return n > 0 && 1162261467 % n === 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Recursion