CODEWITHSUNDEEP
pythonalgorithmrecursion
jeremy radcliff
jeremy radcliff

Reputation: 1109

Double recursion to find smallest multiple using only certain digits

This is the problem statement my question stems from (from Hackerrank): You are given an integer N. Can you find the least positive integer X made up of only 9's and 0's, such that, X is a multiple of N? X is made up of one or more occurences of 9 and zero or more occurences of 0.

I thought I would use double recursion but I'm having trouble understanding how to make it work. My function takes in "multiple", which is a string (so that I can append either '0' or '9' to it in further function calls and not have to deal with arithmetic), and "divisor".

Basically I wanted to keep calling my function, adding either 9 or 0 to "multiple" at every call, returning the final "multiple" when it's finally divisible by "divisor". I was envisioning it as a tree of function calls splitting every time between function(multiple + '9', divisor) and function(multiple + '0', divisor).

However, it seems once I call return, it doesn't get to the second function call:

#multiple is a string
def rec_nine_zero(multiple, divisor):
    if int(multiple) % divisor == 0:
        return multiple
    else:
        return rec_nine_zero(multiple + '9', divisor)
        return rec_nine_zero(multiple + '0', divisor)

The below works:

print(rec_nine_zero('9', 1111))

However, if I try this (where the desired multiple is 90):

print(rec_nine_zero('9', 5)

It crashes and tells me basically that the stack blew up, meaning it never got to the second function call.

One problem I can see is that even if I manage to get the return statement to call both functions (with multiple + '9' and multiple + '0'), I feel like all of the branches of the function call tree except one (the one that finally finds the right result) will keep going until the stack says "annnnd...we're done".

EDIT: Based on Prune's answer, here is my new function:

def rec_nine_zero(multiples, divisor):
    for multiple in multiples:
        if int(multiple) % divisor == 0:
            return multiple
    new_multiples = []
    for multiple in multiples:
        new_multiples.append(multiple + '0')
        new_multiples.append(multiple + '9')
    return rec_nine_zero(new_multiples, divisor)

Upvotes: 1

Views: 231

Answers (2)

hashcode55
hashcode55

Reputation: 5860

Not the answer but heres another simpler way to do the question - 

def rec_nine_zero(divisor):
    d = divisor
    while True:
        if all([True if i in '09' else False for i in `d`]): return d 
        else: d+=divisor

print rec_nine_zero(111)

Anyways to answer your question -

There are some caveats in your code which might give you some tips about recursion.

  • First you have a return statement under another return statement in the same construct and because of this the second return statement is never run.
  • Second thing is you are missing a base case for recursion which is needed to stop the recursion from going on. What your code is doing right now is just appending 9 and 9 and 9 ...., your 1st case works because luckily, 111 has a multiple of 999. In other cases it fails miserably.

And unfortunately, you cannot construct a base case for this problem if you solve it this way. The solution that @Prune gave is the right one.

Hope it helps!

Yeah you got it right! Anyways, I like shortening the code so here you go with the canonical bfs- 

def rec_nine_zero(multiples, divisor):
    que = [];que.append('9')
    while(len(que) != 0):
        k = que.pop()
        if int(k)%divisor == 0:return k
        que.append(k+'9');que.append(k+'0')
    return -1   

print rec_nine_zero('9', 5)

PS - I'm sure it can be shortened more!

Upvotes: 2

Prune
Prune

Reputation: 77827

It blows up because you've done this in the canonical fashion of depth-first search. The first branch you try in a string of 9's, as long as needed to find a solution. Since there isn't any such solution for N=5, you recur until you blow the stack.

Change over to breadth-first. Generate and test your smallest string, '9'. When that fails, recur on the list of strings you want to extend: ["9"].

In the recursion, you append '0' and '9' to each candidate in the list. On the first recursion, this gives you ["90", "99"]. With N=5, you'll return success on this stage. If you have some other number, such as 7, you'll recur with this new list.

On the next step, you'll test the list ["900", "909", "990", "999"], and continue this process until you succeed.

BTW, you can perhaps make this easier if you quit converting between string and int: just start with 9. The next stage will work on 10*x and 10*x+9 for each x in the previous list.

Does that get you moving?

Upvotes: 3

Related Questions