Singpath Python Error. "Your code took too long to return."
Question: I was playing around with the _Singpath_ Python practice questions. And came
across a simple question which asks the following:

    
    
    Given an input of a list of numbers and a high number, 
    return the number of multiples 
    of each of those numbers that are less than the maximum number. 
    For this case the list will contain a maximum of 3 numbers 
    that are all relatively prime to each other.
    

I wrote this simple program, it ran perfectly fine:

    
    
    """
     Given an input of a list of numbers and a high number, 
     return the number of multiples 
     of each of those numbers that are less than the maximum number. 
     For this case the list will contain a maximum of 3 numbers 
     that are all relatively prime to each other.
    
    >>> countMultiples([3],30)
    9
    >>> countMultiples([3,5],100)
    46
    >>> countMultiples([3,5,7],30)
    16
    """
    
    def countMultiples(l, max):
        j = []
        for num in l:
            i = 1
            count = 0
            while num * i < max:
                if num * i not in j:
                    j.append(num * i)
                i += 1
        return len(j)
    
    
    print countMultiples([3],30)
    print countMultiples([3,5],100)
    print countMultiples([3, 5, 7],30)
    

But when I try to run the same on SingPath, it gave me this error

    
    
    Your code took too long to return. 
    Your solution may be stuck in an infinite loop. Please try again.
    

Has anyone experienced the same issues with Singpath?


Answer: I suspect the error you're getting means exactly what it says. For some input
that the test program gives your function, it takes too long to return. I
don't know anything about singpath myself, so I don't know exactly how long
that might be. But I'd guess that they give you enough time to solve the
problem if you use the best algorithm.

You can see for yourself that your code is slow if you pass in a very large
`max` value. Try passing `10000` as `max` and you may end up waiting for a
minute or two to get a result.

There are a couple of reasons your code is slow in these situations. The first
is that you have a `list` of every multiple that you've found so far, and you
are searching the list to see if the latest value has already been seen. Each
search takes time proportional to the length of the list, so for the whole run
of the function, it takes quadratic time (relative to the result value).

You could improve on this quite a lot by using a `set` instead of a `list`.
You can test if an object is in a `set` in (amortized) constant time. But if
`j` is a set, you don't actually need to test if a value is already in it
before adding, since `set`s ignore duplicated values anyway. This means you
can just `add` a value to the set without any care about whether it was there
already.

    
    
    def countMultiples(l, max):
        j = set()                    # use a set object, rather than a list
        for num in l:
            i = 1
            count = 0
            while num * i < max:
                j.add(num*i)         # add items to the set unconditionally
                i += 1
        return len(j)                # duplicate values are ignored, and won't be counted
    

This runs a fair amount faster than the original code, and `max` values of a
million or more will return in a not too unreasonable time. But if you try
values larger still (say, 100 million or a billion), you'll eventually still
run into trouble. That's because your code uses a loop to find all the
multiples, which takes linear time (relative to the result value).
Fortunately, there is a better algorithm.

(If you want to figure out the better approach on your own, you might want to
stop reading here.)

The better way is to use division to find how many times you can multiply each
value to get a value less than `max`. The number of multiples of `num` that
are strictly less than `max` is `(max-1) // num` (the `-1` is because we don't
want to count `max` itself). Integer division is much faster than doing a
loop!

There is an added complexity though. If you divide to find the number of
multiples, you don't actually have the multiples themselves to put in a `set`
like we were doing above. This means that any integer that is a multiple of
more than than one of our input numbers will be counted more than once.

Fortunately, there's a good way to fix this. We just need to count how many
integers were over counted, and subtract that from our total. When we have two
input values, we'll have double counted every integer that is a multiple of
their least common multiple (which, since we're guaranteed that they're
relatively prime, means their product).

If we have three values, We can do the same subtraction for each pair of
numbers. But that won't be exactly right either. The integers that are
multiples of all three of our input numbers will be counted three times, then
subtracted back out three times as well (since they're multiples of the LCM of
each pair of values). So we need to add a final value to make sure those
multiples of all three values are included in the final sum exactly once.

    
    
    import itertools
    
    def countMultiples(numbers, max):
        count = 0
        for i, num in enumerate(numbers):
            count += (max-1) // num       # count multiples of num that are less than max
        for a, b in itertools.combinations(numbers, 2):
            count -= (max-1) // (a*b)     # remove double counted numbers
        if len(numbers) == 3:
            a, b, c = numbers
            count += (max-1) // (a*b*c)   # add the vals that were removed too many times
        return count
    

This should run in something like constant time for any value of `max`.

Now, that's probably as efficient as you need to be for the problem you're
given (which will always have no more than three values). But if you wanted a
solution that would work for more input values, you can write a general
version. It uses the same algorithm as the previous version, and uses
`itertools.combinations` a lot more to get different numbers of input values
at a time. The number of products of the LCM of odd numbers of values get
added to the count, while the number of products of the LCM of even numbers of
values are subtracted.

    
    
    import itertools
    from functools import reduce
    from operator import mul
    
    def lcm(nums):
        return reduce(mul, nums)   # this is only correct if nums are all relatively prime
    
    def countMultiples(numbers, max):
        count = 0
        for n in range(len(numbers)):
            for nums in itertools.combinations(numbers, n+1):
                count += (-1)**n * (max-1) // lcm(nums)
        return count
    

Here's an example output of this version, which is was computed very quickly:

    
    
    >>> countMultiples([2,3,5,7,11,13,17], 100000000000000)
    81947464300342
    

