Leetcode 326 - Power of Three

DocumentsAlgorithms
Algorithms, Leetcode, Python
Catalogue
  1. 1. Question
  2. 2. Explanation
  3. 3. Code

Question

Given an integer, write a function to determine if it is a power of three.

Example 1:

Input: 27
Output: true
Example 2:

Input: 0
Output: false
Example 3:

Input: 9
Output: true
Example 4:

Input: 45
Output: false

Follow up:
Could you do it without using any loop / recursion?

Explanation

判断一个数 n 是不是3的幂，只需要以3为底求 n 的对数即可，是正整数返回 True ，否则返回 False 。代码中 log() 默认以 $e$ 为底，因此需要用到换底公式：
$$
log_{\theta}{n} = \frac{log_{\epsilon}{n}}{log_{\epsilon}{\theta}}
$$
在 Python 中，由于精度的问题，求3为底 n 的对数可能得到不精确的结果，例如:

1
2
>>> log(243,3)
>>> 4.999999999

因此需要将求出的对数四舍五入后作为3的指数求出结果，将结果和 n 对比，如果相等，则 n 是3的幂。

Code

1
2
3
4
5
6
7
8
9
10
11
from math import log

class Solution(object):
    def isPowerOfThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n > 0:
            return 3**round(log(n,3)) == n
        return False
Comments