481. Calculate (x^y)%z without using pow() function

Problem: Given integers x, y, and z. Write a program to calculate (x^y)%z without pow() function.

Example:

x = 2, y= 5, z = 3
Output: (2 ^ 5) % 3 = 2

x = 5, y= 55, z = 221
Output: (5 ^ 55) % 221 = 112

Approach:

Straight forward way to calculate the x^y and then do the MOD with z but there is a problem with this approach. If x^y is big enough to cross the boundary of Integer.MAX then we cannot calculate. Instead, it can do the MOD at each step in the calculation of x^y. This will not change our final result. Let's see why?

x = 2, y = 8, z = 7
2^8 = 256%7 = 4

Let's see at each step
2^1 = 2 % 7 = 2
2^2 = 2*2 % 7 = 4
2^3 = 4*2 % 7 = 1 (8%7=1)
2^4 = 1*2 % 7 = 2
2^5 = 2*2 % 7 = 4
2^6 = 4*2 % 7 = 1 (8%7=1)
2^7 = 2 % 7 = 2
2^8 = 2*2 % 7 = 4

As we can see, doing MOD at each step will not affect the final result. Now for calculating x^y, the easiest way is multiply x, y times but this will have time complexity O(y), this can be reduced to O(logy) - please refer - calculate power(k,n).

Output:

(2 ^ 8) % 7 = 4

Reference:https://www.careercup.com/question?id=22767685