278. Power of Three
You receive a single integer n. Decide whether n can be written as 3^k for some integer k >= 0, and return true or false accordingly.
The powers of three begin at 3^0 = 1 and continue 3, 9, 27, 81, … Keep in mind that n may be zero or negative, and no power of three is ever zero or negative.
Follow-up: can you answer without any loop or recursion at all?
Example 1:
Input: n = 27
Output: true
Explanation: 27 = 3 × 3 × 3 = 3^3, so it is a power of three.
Example 2:
Input: n = 0
Output: false
Explanation: 3^k is positive for every k >= 0, so 0 can never be a power of three.
Example 3:
Input: n = 45
Output: false
Explanation: 45 = 3^2 × 5. The stray factor of 5 means it is not a pure power of three.
Constraints:
- -2³¹ ≤ n ≤ 2³¹ - 1
Hints:
If n really is 3^k, dividing it by 3 repeatedly (while the remainder is 0) must walk it all the way down to exactly 1.
The same test reads naturally as recursion: n is a power of three when n == 1, or when n is divisible by 3 and n / 3 is itself a power of three.
Loop-free: 3^19 = 1162261467 is the largest power of three that fits in 32 bits, and because 3 is prime, every divisor of 3^19 is itself a power of three. So the whole answer is n > 0 and 1162261467 % n == 0.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 27
Expected output: true