2023-10-23|閱讀時間 ‧ 約 3 分鐘

應用題 判斷輸入是否為4^k Leetcode 342: Power of Four

題目敘述

這題的題目會給我們一個輸入整數,要求我們判斷這個整數是否可以用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

分享至
成為作者繼續創作的動力吧!
從 Google News 追蹤更多 vocus 的最新精選內容從 Google News 追蹤更多 vocus 的最新精選內容

作者的相關文章

小松鼠的演算法樂園 的其他內容

你可能也想看

發表回應

成為會員 後即可發表留言
© 2024 vocus All rights reserved.