Fast Power

Question

Calculate the a^n % b where a, b and n are all 32bit integers.

O(log(n))

Analysis

32bit? overflow

Thoughts

这一题主要考察的是如何达到logn和如何处理integer overflow的问题

对于log(n)算 power的算法，可以拆分为二分法 fast power

(a * b) % p = (a % p * b % p) % p

对于这道题,还有两个特殊情况，power 0,1的时候

Solution

class Solution:
    """
    @param a, b, n: 32bit integers
    @return: An integer
    """
    def fastPower(self, a, b, n):
        # write your code here
        if n == 0:
            return 1 % b
        if n == 1:
            return a % b
        product = self.fastPower(a, b, n / 2)
        product *= product
        product = product % b
        #if n is odd
        if n % 2 == 1:
            product = product * a % b
        return product