Example
For 231 % 3 = 2
For 1001000 % 1000 = 0
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