Power of Three
Easy · Backtracking · Math · Recursion
Problem
Given an integer n, return true if it is a power of three and false otherwise.
n is a power of three when there is an integer x >= 0 with n == 3^x. So 1, 3, 9, 27, ... are powers of three. Zero and negative numbers never are.
Examples
Input: n = 27 Output: true
27 = 3^3.
Input: n = 45 Output: false
45 = 3^2 · 5 has the factor 5.
Input: n = 1 Output: true
1 = 3^0, so it counts.
Constraints
- -2^31 <= n <= 2^31 - 1
Approaches
- Divide by three while you can — time O(log n), space O(1)
Follow-up
Can you do it without loops or recursion? Because 3 is prime, the divisors of 3^19 are exactly 3^0 ... 3^19, so n > 0 and 3^19 % n == 0 decides it in one step. The same trick works for any prime base, but not for 4 or 6, whose powers share divisors with other numbers.
Related problems
Start free on Cariara · Coding problems · System design studio
