Pythonで与えられた値が3の冪乗かを判定するプログラムの話。(LeetCode)

• 冪乗のお話。
• 解答

冪乗のお話。

3の冪乗かどうかを判定するプログラムを求められました。

326. Power of Three

整数型の値、nが引数として与えられた場合、それが3の冪乗かを判定し、冪乗ならばTrue、冪乗でなければFalseを返してください、っていう問題です。
なお、nの値には以下の制約が存在します。

-2^31 <= n <= 2^31 - 1

さて、どうしましょう？ってことでメモ。

解答

とりあえず解ける解答。

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n == 0:
            return False
        if n == 1:
            return True
        for i in range(31):
            if pow(3,i) == n:
                return True
        return False
# Runtime: 240 ms, faster than  5.15%  of  Python3  online submissions for  Power of Three.
# Memory Usage: 14.4 MB, less than  13.91%  of  Python3  online submissions for  Power of Three.

pow関数を使っています。

pow関数は引数に(基数、冪乗)を取っています。ここでの使い方は、31乗までを範囲としているため、for文で1~31までの値を回します。
pow(3,1) == n
pow(3,2) == n
.............
といったように3の1乗から31乗までを調べます。

ただし、31という値を意識しすぎる余り、かなり遅くなっています。
遅い理由としては、正しくない場合、31回も回すことになっているからです。

しかし、解けるだけでいいのであればこれでも良いことになります。

では、速度を意識してみましょう。

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n < 1:
            return False
        while n % 3 == 0:
            n /= 3
        return n == 1
#Runtime: 68 ms, faster than 87.60% of Python3 online submissions for Power of Three.
#Memory Usage: 14.3 MB, less than 46.96% of Python3 online submissions for Power of Three.

こちらの場合、while文で書き直しています。
そして、仮にnを3で割った時の値が0ではない場合、即判定が打ち切られます。
それゆえに最悪の場合に31回回すよりも高速化できています。

こんな感じ。最悪の場合に着目してアルゴリズムを設計する重要性を再確認しました。

今回はここまで。