Modular Expression

Implement pow(A, B) % C.

In other words, given A, B and C,
find (AB)%C.

Input : A = 2, B = 3, C = 3
Return : 2 
2^3 % 3 = 8 % 3 = 2
Method1:

Time: O(logn)
Space: O(1)

public class Solution {
    public int Mod(int A, int B, int C) {
        if (B == 0) return 1 % C;
        boolean negative = (A < 0) && ((B & 1) == 1);
        long a = A;
        long result = 1;
        while (B > 0) {
            if ((B & 1) == 1) {
                result = (result * a) % C;
            }
            a = (a * a) % C;
            B = B >> 1;
        }
        if (negative) result = (long) C + result;
        return (int) result;
    }
}