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