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

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 2

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