題目出處

140 · Fast Power

難度

medium

個人範例程式碼

class Solution:
    """
    @param a: A 32bit integer
    @param b: A 32bit integer
    @param n: A 32bit integer
    @return: An integer
    """
    def fast_power(self, a: int, b: int, n: int) -> int:
        ans, tmp = 1, a 
        while(n > 0):
            if(n % 2 == 1):
                ans = (ans * tmp) % b

            tmp = (tmp * tmp) % b 
            n = n // 2
        else:
            return ans % b

算法說明

• 有非常類似的問題，詳細說明可參考：【Leetcode】python – [50] Pow(x, n) 個人解法筆記

核心概念為，將 n 次方拆成二進位的方式計算 (這樣就不用重複算)

例如 9 = 8 + 0 + 0 + 1，

我們只重複計算 1^2^2^2^2…. 可以減少一半的計算次數，複雜度為 O(n) -> O(logN)

另外處理負數要特別注意。

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

處理輸入 n = 0 ，return 1,
與輸入 n < 0 ，作負數處理。

Boundary conditions

循環直到當 n 0 時 ( 1//2 = 0 )

Reference

• 快速幂 · Fast Power