Be the first user to complete this post
|
Add to List |
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