721. Check if a Number is a Power of 3

Given an integer n, determine whether it is a power of 3. A positive integer is a power of 3 if there exists an integer k >= 0 such that n = 3^k. Return true if n is a power of 3, otherwise return false. Zero and negative numbers are NOT powers of 3. Implement the check recursively.

Input: A single integer n.

Output: Return a boolean: true or false (lowercase).

Examples

Input: 27
Output: true
Explanation: 27 = 3^3.

Input: 45
Output: false
Explanation: 45 is not a power of 3.

Input: 1
Output: true
Explanation: 1 = 3^0.

Constraints

• -10^9 <= n <= 10^9

Asked by