題目

難度：★☆☆☆☆
類型：數(shù)學(xué)

給定一個整數(shù)，寫一個函數(shù)來判斷它是否是 3 的冪次方。

進(jìn)階：
你能不使用循環(huán)或者遞歸來完成本題嗎？

示例

示例 1:
輸入: 27
輸出: true

示例 2:
輸入: 0
輸出: false

示例 3:
輸入: 9
輸出: true

示例 4:
輸入: 45
輸出: false

解答

這道題跟【題目231. 2的冪】屬于同一個類型，遞歸和迭代寫法可以直接參考該題目，這里為大家介紹一種時間和空間復(fù)雜度均為O(1)的解法。

我們知道，輸入是32位有符號整數(shù)，范圍是[-2^31~231-1]，即[-2147483648~2147483647]，在這個范圍內(nèi)3的冪是有限的，而且最大的是3^19=1162261467，這個最大的3的冪除以其他任何一個3的冪，余數(shù)一定是0，而除以任何一個不是3的冪的數(shù)，則余數(shù)一定不為零，根據(jù)這個原理，我們就可以解決3的冪的判別問題。

class Solution(object):
    def isPowerOfThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n > 0 and 3 ** 19 % n == 0

如有疑問或建議，歡迎評論區(qū)留言~