Implement Power Function

Implement pow(x, n) % d.

In other words, given x, n and d,

find (x^n % d)

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);
    }
}