Fast Power

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)

------------------- thinking -----------------------------------------
result * base & base * base might overflow, so please use long long as the type of these two variables
-------------------- codes -------------------------------------------
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 == 0) {
            return 1 % b;
        }
        if (n == 1) {
            return a % b;
        }
        long long base = a % b;
        long long result = 1;
        int bit_n = n;
        while (bit_n > 0) {
            if (bit_n % 2) {
                result = (result * base) % b;
            }
            bit_n = bit_n/2;
            base = (base * base) % b;
        }
        return result;
    }
};