CLEAN CODE MODULAR EXPRESSION: BACKTRACKING | RECURSION

By: Saurav

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.

Algo:

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


Let me know what you think!
twitter: sprakash24oct
linkedin

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 :)