304. Power of Three Climb
A storage depot only accepts pallets whose crate count is a power of three: 1, 3, 9, 27, 81, and so on. A clerk receives a single integer n describing a delivery and has to decide whether the depot can take it.
Return true if there is a non-negative integer x such that 3x == n, and false otherwise. Zero and negative counts are never accepted. Try to solve it recursively: a number is acceptable if it is 1, or if it is divisible by 3 and one third of it is acceptable.
Example 1
- Input:
- n = 243
- Output:
- true
- Explanation:
243 = 3 x 3 x 3 x 3 x 3, so the delivery is accepted.
Example 2
- Input:
- n = 252
- Output:
- false
- Explanation:
252 is divisible by 3 once, giving 84, then 28, which is not divisible by 3 and is not 1, so it is rejected.
Constraints
-231 ≤ n ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(log n)