題目敘述
這題的題目會給我們一個輸入整數，要求我們判斷這個整數是否可以用4^k 的形式來表達?
詳細的題目可在這裡看到
測試範例
Example 1:Input: n = 16
Output: true
Example 2:
Input: n = 5
Output: false
Example 3:
Input: n = 1
Output: true
約束條件
Constraints:
-231<= n <= 231- 1
Follow up: Could you solve it without loops/recursion?
演算法
除了比較直覺的不斷除以四，判斷是否能剛好整除4的相除法之外。
class Solution:
def isPowerOfFour(self, num):
while num > 1:
if num % 4 != 0:
return False
num /= 4
return num == 1
還有位元操作結合同餘3的判斷法。
首先，先排除小於等於0的整數，因為<=0的整數不可能是4^k。
4^k一定是2的冪，也一定可以用2^n次方來表達。
接著，用num bitwiseAND (num-1) == 0 去判斷是否為2^n。
(這是因為二進位表達式中，2^k只會有一個bit1出現)
最後，用同餘的關係，4^k mod 3 = (3+1)^k mod 3 = 1^k mod 3 = 1 判斷整除3是否同餘1。假如是，那麼這個輸入整數就可以用4^k形式來表達。
程式碼
class Solution:
def isPowerOfFour(self, n: int) -> bool:
return n > 0 and (n & (n - 1)) == 0 and (n % 3 == 1)
複雜度分析
時間複雜度:
O( 1 ) 固定長度32bits的位元操作，和mod 3同餘1的判斷
空間複雜度:
O(1) 都是固定尺寸的臨時變數，所占用的記憶體空間為常數級別。
Reference
[1] Python O( log n ) sol. based on bit-manipulation, run time 90%+ - Power of Four - LeetCode
