Online Judge Solutions

Saturday, December 13, 2014

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)

 
class Solution {
public:
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    int fastPower(int a, int b, int n) {
        
        long long  x = 1;
        // long is ok only for some platform for the case where b is INT_MAX
        long long pow = a % b;
        while(n) {
            if (n & 1) {
                x = (x * pow) % b;
            }
            pow = (pow * pow) % b;
            n >>= 1;
        }
        
        return x % b;
    }
};

No comments:

Post a Comment