Decomposing a number as a sum of two products using tree recursion

Question

Below is the problem taken from page6 here.

The TAs want to print handouts for their students. However, for some unfathomable reason, both the printers are broken; the first printer only prints multiples of n1, and the second printer only prints multiples of n2. Help the TAs figure out whether or not it is possible to print an exact number of handouts! First try to solve without a helper function. Also try to solve using a helper function and adding up to the sum.

def has_sum(sum, n1, n2):
"""
>>> has_sum(1, 3, 5)
False
>>> has_sum(5, 3, 5) # 1(5) + 0(3) = 5
True
>>> has_sum(11, 3, 5) # 2(3) + 1(5) = 11
True
"""

Solution

I think there is no mathematical solution except bruteforce recursion.

def f(sum, n1, n2):
    """
    >>> f(1, 3, 5)
    False
    >>> f(5, 3, 5) # 1(5) + 0(3) = 5
    True
    >>> f(11, 3, 5) # 2(3) + 1(5) = 11
    True
    >>> f(189, 4, 9)
    True
    """
    memoiz = []
    value = []   
    def has_sum(sum, n1, n2, x=0, y=0):
        if x == 0 and y == 0:
            value.append(n1)
            value.append(n2)   #execute once to reuse tup
        if (n1 + n2)  == sum:
            return True
        if (memoiz) and ((n1 + n2)  > sum): # inefficient base case, need to improve using math
            return False
        result1 = False
        result2 = False
        if (x+1, y) not in memoiz:
            memoiz.append((x+1, y)) #memoiz
            result1 = has_sum(sum, (x+1)*value[0], y*value[1], x+1, y)
        if (x, y+1) not in memoiz:
            memoiz.append((x, y+1)) #memoiz
            result2 = has_sum(sum, x*value[0], (y+1)*value[1], x, y+1)
        return result1 or result2
    return has_sum(sum, n1, n2)

Can we improve the base case that returns False?

Answer 1

First try to solve without a helper function. Also try to solve using a helper function and adding up to the sum.

You haven't included an implementation without a helper function. You implemented memoization, which was not part of the description. In any case, memoization won't be possible without a helper function or annotations.

Code review

There are several problems with your implementation:

• memoiz shouldn't be a list, but a set
• The value variable is confusing: it merely stores the original values of n1 and n2, you could simply save those values before calling the helper function
• sum is a poor name for a variable, because it shadows the built-in named "sum"
• There should be spaces around operators to improve readability, for example instead of (x+1)*value[0] it should be (x + 1) * value[0]
• Instead of multiplying value[0] and value[1], it would be better to accumulate a sum
• If result1 is True, there's no need to evaluate result2

With the above tips, the solution can be simplified a bit and become more efficient:

memoiz = set()
def has_sum(sum, n1, n2, x=0, y=0):
    if n1 + n2 == sum:
        return True
    if n1 + n2 > sum:
        return False
    if (x+1, y) not in memoiz:
        memoiz.add((x+1, y))
        result1 = has_sum(sum, n1 + orig_n1, n2, x+1, y)
        if result1:
            return True
    if (x, y+1) not in memoiz:
        memoiz.add((x, y+1))
        return has_sum(sum, n1, n2 + orig_n2, x, y+1)
    return False
orig_n1, orig_n2 = n1, n2
return has_sum(sum, 0, 0)

An alternative solution

Consider this alternative algorithm:

• If target is 0, then we can reach it by 0 times n1 and n2
• If target is below 0, then we cannot reach it
• If target can be reached by a sum of multiples of n1 and n2, then target - n1 or target - n2 must be reachable too

Implementation using memoization:

memoize = { 0: True }
def helper(target):
    if target not in memoize:
        if target < 0:
            memoize[target] = False
        else:
            memoize[target] = helper(target - n1) or helper(target - n2)
    return memoize[target]
return helper(target)

Iterative solution

At first I overlooked your requirement of a recursive solution. For the record, this was my original suggestion using iterative logic.

---

Unless I'm missing something, you can solve this using a much simpler algorithm:

• If a solution exists, then sum == n1 * A + n2 * B where A and B are integers
• Loop from A = 0 to sum, by steps of n1
• If sum - A is divisible by n2, then a solution exists
• If the end of the loop is reached, then a solution doesn't exist

That is:

for A in range(0, sum + 1, n1):
    if (sum - A) % n2 == 0:
        return True
return False