Code challenge: finding the divisible in a list

Question

I am playing a code challenge. Simply speaking, the problem is:

Given a list L (max length is of the order of 1000) containing positive integers. Find the number of "Lucky Triples", which is L[i] divides L[j], and L[j] divides L[k].

for example, [1,2,3,4,5,6] should give the answer 3 because [1,2,4], [1,2,6],[1,3,6]

My attempt:

1. Sort the list. (let say there are n elements)
2. 3 For loops: i, j, k (i from 1 to n-2), (j from i+1 to n-1), (k from j+1 to n)
3. only if L[j] % L[i] == 0, the k for loop will be executed

The algorithm seems to give the correct answer. But the challenge said that my code exceeded the time limit. I tried on my computer for the list [1,2,3,...,2000], count = 40888(I guess it is correct). The time is around 5 second.

Is there any faster way to do that?

This is the code I have written in python.

def answer(l):
    l.sort()
    cnt = 0
    if len(l) == 2:
        return cnt
    for i in range(len(l)-2):
        for j in range(1,len(l)-1-i):
            if (l[i+j]%l[i] == 0):
                for k in range(1,len(l)-j-i):
                    if (l[i+j+k]%l[i+j] == 0):
                        cnt += 1

    return cnt

Answer 1

Thank you guys for all your suggestions. They are brilliant. But it seems that I still can't pass the speed test or I cannot handle with duplicated elements.

After discussing with my friend, I have just come up with another solution. It should be O(n^2) and I passed the speed test. Thanks all!!

def answer(lst):
    lst.sort()
    count = 0
    if len(lst) == 2:
        return count

    #for each middle element, count the divisors at the front and the multiples at the back. Then multiply them.
    for i, middle in enumerate(lst[1:len(lst)-1], start = 1):
        countfirst = 0
        countthird = 0
        for first in (lst[0:i]):
            if middle % first == 0:
                countfirst += 1
        for third in (lst[i+1:]):
            if third % middle == 0:
                countthird += 1
        count += countfirst*countthird

    return count

Answer 2

Your original code, for reference.

def answer(l):
    l.sort()
    cnt = 0
    if len(l) == 2:
        return cnt
    for i in range(len(l)-2):
        for j in range(1,len(l)-1-i):
            if (l[i+j]%l[i] == 0):
                for k in range(1,len(l)-j-i):
                    if (l[i+j+k]%l[i+j] == 0):
                        cnt += 1

    return cnt

There are a number of misimplementations here, and with just a few tweaks we can probably get this running much faster. Let's start:

def answer(lst):  # I prefer not to use `l` because it looks like `1`
    lst.sort()
    count = 0  # use whole words here. No reason not to.
    if len(lst) == 2:
        return count
    for i, first in enumerate(lst):
        # using `enumerate` here means you can avoid ugly ranges and
        # saves you from a look up on the list afterwards. Not really a
        # performance hit, but definitely looks and feels nicer.
        for j, second in enumerate(lst[i+1:], start=i+1):
            # this is the big savings. You know since you sorted the list that
            # lst[1] can't divide lst[n] if n>1, but your code still starts
            # searching from lst[1] every time! Enumerating over `l[i+1:]`
            # cuts out a lot of unnecessary burden.
            if second % first == 0:
                # see how using enumerate makes that look nicer?
                for third in lst[j+1:]:
                    if third % second == 0:
                        count += 1
    return count

I bet that on its own will pass your speed test, but if not, you can check for membership instead. In fact, using a set here is probably a great idea!

def answer2(lst):
    s = set(lst)
    limit = max(s)  # we'll never have a valid product higher than this
    multiples = {}  # accumulator for our mapping
    for n in sorted(s):
        max_prod = limit // n  # n * (max_prod+1) > limit
        multiples[n] = [n*k for k in range(2, max_prod+1) if n*k in s]
        # in [1,2,3,4,5,6]:
        # multiples = {1: [2, 3, 4, 5, 6],
        #              2: [4, 6],
        #              3: [6],
        #              4: [],
        #              5: [],
        #              6: []}

    # multiples is now a mapping you can use a Depth- or Breadth-first-search on
    triples = sum(1 for j in multiples
                    for k in multiples.get(j, [])
                    for l in multiples.get(k, []))
    # This basically just looks up each starting value as j, then grabs
    # each valid multiple and assigns it to k, then grabs each valid
    # multiple of k and assigns it to l. For every possible combination there,
    # it adds 1 more to the result of `triples`
    return triples

Answer 3

I guess sorting the list is pretty inefficient. I would rather try to iteratively reduce the number of candidates. You could do that in two steps.

At first filter all numbers that do not have a divisor.

from itertools import combinations
candidates = [max(pair) for pair in combinations(l, 2) if max(pair)%min(pair) == 0]

After that, count the number of remaining candidates, that do have a divisor.

result = sum(max(pair)%min(pair) == 0 for pair in combinations(candidates, 2))

Answer 4

You can use additional space to help yourself. After you sort the input list you should make a map/dict where the key is each element in the list and value is a list of elements which are divisible by that in the list so you would have something like this assume sorted list is list = [1,2,3,4,5,6] your map would be

 1 -> [2,3,4,5,6]
 2-> [4,6]
 3->[6]
 4->[]
 5->[]
 6->[]

now for every key in the map you find what it can divide and then you find what that divides, for example you know that

1 divides 2 and 2 divides 4 and 6, similarly 1 divides 3 and 3 divides 6

the complexity of sorting should be O(nlogn) and that of constructing the list should be better than O(n^2) (but I am not sure about this part) and then I am not sure about the complexity of when you are actually checking for multiples but I think this should be much much faster than a brute force O(n^3)

If someone could help me figure out the time complexity of this I would really appreciate it

EDIT :

You can make the map creation part faster by incrementing by X (and not 1) where X is the number in the list you are currently on since it is sorted.

Answer 5

I'll give you just an idea, the implementation should be up to you:

1. Initialize the global counter to zero.
2. Sort the list, starting with smallest number.
3. Create a list of integers (one entry per number with same index).
4. Iterate through each number (index i), and do the following:
5. Check for dividers at positions 0 to i-1.
6. Store the number of dividers in the list at the position i.
7. Fetch the number of dividers from the list for each divider, and add each number to the global counter.
8. Unless you finished, go to 3rd.
9. Your result should be in the global counter.