Lintcode: Fast Power

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

Have you met this question in a real interview? 

Yes

Example

For 231 % 3 = 2

For 1001000 % 1000 = 0

Challenge

O(logn)

Tags Expand 

Divide and Conquer

百科--取模
Modular operation has this property: (a * b) % p = (a % p * b % p) % p 
Divide and conquer.
Note the type of product is long in case of overflow
Reference: http://algorithm.yuanbin.me/math_and_bit_manipulation/fast_power.html
Divide and conquer
Time: O(log2n)
Space: O(log2n)

class Solution {
public:
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    int fastPower(int a, int b, int n) {
        // write your code here
        if(n == 1) return a % b;
        else if(n == 0) return 1 % b;
        
        long product = fastPower(a, b, n / 2);
        product = product * product % b;
        if(n % 2) product = product * a % b;
        return product;   
    }
};

// n == 1 condition is not necessary