2018-02-23 01:12:00 UTC
Implement pow(A, B) % C.
In other words, given A, B and C, find (AB)%C.
This is a nice case of recursion. But it's better to invest some time in it.
If a is 0 -> return 0
if b is 0 -> return 1%c
Otherwise, write the base case of b == 1 and two recursive cases of odd and even b. We could have written simple case of b-1 and 1 but, in even case we can even enhance the solution by dividing b in to b/2 and b/2 in the recursion tree as shown in the code. Lets write the tests first
p mod(0,0,3) == 0 p mod(1,0,3) == 1 p mod(3,3,3) == 0
def mod(a, b, c) return 0 if a == 0 return 1%c if b == 0 if b <= 1 return a%c else if b%2 == 0 r = mod(a, b/2, c) return ( r* r)%c else return (a%c * mod(a, b-1, c))%c end end end
Owned & Maintained by Saurav Prakash
If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)