leetcode

どーも!

たかぽんです!

今回もやっていきます!

342. Power of Four

さて...

この手の問題こないだ見たな・・・?

問題は以下です。

問題の内容としては、与えられた値が4の乗数になっているか?

つまり、1, 4, 16, 64....であるか?って言うことですね。

これに関しては、以前解いた問題とほぼ一緒の形式だったので、楽ちんでした...!

アルゴリズム

さて、アルゴリズムを考えます。

と...いいたのですが、ほとんど以下と同じです...w

一応、改めて簡単に。

今回の場合、与えられた数値を4で割り続け、最終的に1になれば大丈夫なはずです。

そして、4の倍数を4で割った場合、常に余りは0になります。

一度でも割り切れない値が出ない限りは余りは常に0になるはずなので、その性質をつかって回答していきます。

つまり...

余りが0の間はずっと4で割り続け、n/4を繰り返していくと...

最終的に1/4 = 0あまり1になるはずです。

そこでループを出たタイミングでnが1であれば、4で割ったあとの数が1だったので、それは4の倍数なので、trueと言えます。

そうでない場合はfalseですね。

ただ、一点だけ気をつけないといけないのが、0の場合です。

0の場合、0/4 = 0あまり0です。

そのため、無限ループしてしまうんですね...

そのため、早めにreturnしておきます。

提出したコード

以下、提出したコードです。

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


# 結果
Runtime: 28 ms, faster than 87.70% of Python3 online submissions for Power of Four.
Memory Usage: 14.2 MB, less than 72.03% of Python3 online submissions for Power of Four.
おすすめの記事