Tuesday, May 12, 2015

[LintCode] Fast Power

Calculate the an % b where a, b and n are all 32bit integers.
Example
For 231 % 3 = 2
For 1001000 % 1000 = 0
Challenge
O(logn)
Note the nature of MOD and overflow
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(1 == b) return 0;
        if(0 == n) return 1;
        long c = fastPower(a, b, n/2);
        if(n%2)
        {
            return (((c*c)%b)*(a%b))%b;   
        }
        return (c*c)%b;
    }
};