Note that remainders on division cannot be negative. In other words, make sure the answer you return is non negative.
Input : x = 2, n = 3, d = 3
Output : 2
2^3 % 3 = 8 % 3 = 2.
思路:
We know that x ^ n = (x * x) ^ (n / 2) if n is even. so we can keep multiplying x and dividing n by 2. Note that if n is odd, we need to multiply x once to the result.
Solution:
Time: O(logn) Space: O(1)
public class Solution { public int pow(int x, int n, int d) { // 2 3 5 = 2 ^ 3 % 5 = 8 % 5 = 3 // loop 1: r = 2, a = 4, n = 1 // loop 2: r = 8, a = 16, n = 0 if (x < 0) x = (x + d) % d; long a = x; long result = 1; while (n > 0) { if (n % 2 == 1) { result = (result * a) % d; } a = (a * a) % d; n = n >> 1; } return (int) (result % d); } }