leetcode

どーも!

たかぽんです!

今回もやっていきます!

326. Power of Three

今回の問題はPower of Threeと言う問題をやっていきます!

この問題は、与えられたINT型の値が3の乗数になっているかどうかを判定するプログラムを書け....というものです。

27なら3^3で表すことができるので、true, 1も3^0でtrue, 45は3^2 * 5になるので、falseです。

頭では理解できるけど、意外と難しいですね...!

ではアルゴリズムを検討していきましょう。

アルゴリズム

さて、それではアルゴリズムを考えていきます。

以下の画像をご覧ください。

45と27を割ったあまりをザーッと書き出したものです。

3の乗数になっているものは常にあまりが0になりますね。

さらに言うと、最後は絶対に3/3 = 1(あまりは0)になります。

そのため、そのあと1/3をすると、0・・・1ですね。

それとくらべ、割り切れない場合はいずれあまりが出てきて、最終的には5/3 = 1.***と、綺麗に1にはならなそうです。

つまり...

あまりが0の間、3で割り続け、最後のnの値が1になってれば大丈夫そうです。

ただ、一点だけ、0の場合のみちょっと特殊なため、別で条件を切ってあげる必要があります。

では、最後に上記をコードに置き換えたものを置いておきます。

提出したコード

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n == 0:
            return 0
        while n % 3 == 0:
            n = n / 3
        if n == 1:
            return 1
        return 0


# 以下結果
Runtime: 72 ms, faster than 81.23% of Python3 online submissions for Power of Three.
Memory Usage: 14.4 MB, less than 16.72% of Python3 online submissions for Power of Three.

おすすめの記事