**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 = 72^8 = 256%7 = 4Let'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).

**Complete Code:**

**Output:**

(2 ^ 8) % 7 = 4