どーも!
たかぽんです!
今回もやっていきます!
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.