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