Code issue: finding a dividend in a list

Question

I play a code call. Simply put, the problem is that:

Given a list L (maximum length of the order of 1000) containing positive integers. Find the number of “Lucky Triples” that 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:

• Sort list. (suppose there are n elements)
• 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)
• only if L[j] % L[i] == 0 will k for loop be executed

The algorithm seems to give the correct answer. But the problem was that my code exceeded the time limit. I tried on my computer the list [1,2,3,...,2000] , count = 40888 (I think this is correct). The time is about 5 seconds.

Is there a faster way to do this?

This is code 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)-ji): if (l[i+j+k]%l[i+j] == 0): cnt += 1 return cnt 

Answer 1

You can use the extra space to help yourself. After sorting the input list, you should do map/dict , where the key is each element in the list, and the value is the list of elements that are divided into a list in the list, so you have something like this, suppose the sorted list is list = [1,2,3,4,5,6] your card will be

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

now for each key on the map you find what it can share, and then you find what separates, for example, you know that

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

sorting complexity should be O(nlogn) , and list building should be better than O(n^2) (but I'm not sure about this part), and then I'm not sure about complexity when you actually check for factors, but I think it should be much faster than the brute force O(n^3)

If someone can help me understand the time complexity of this, I would really appreciate

EDIT:

You can make the map creation part faster by increasing by X (rather than 1), where X is the number in the list that you are currently using after sorting it.

Answer 2

I find sorting a list to be pretty inefficient. I would rather try to iteratively reduce the number of candidates. You can do this in two steps.

First, filter out all numbers that don't 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 who have a divisor.

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

Answer 3

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)-ji): if (l[i+j+k]%l[i+j] == 0): cnt += 1 return cnt 

There are several flaws here, and with just a few tweaks, we can speed up this launch. Let the beginning:

 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 the speed test itself will pass, but if not, you can check the membership instead. In fact, using the kit 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 4

Thanks guys for all your suggestions. They are brilliant. But it seems that I still can’t pass the speed test, or I can’t handle duplicate items.

After discussing with my friend, I just came up with a different solution. It should be O (n ^ 2), and I passed the speed test. Thanks everyone!

 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 5

I will give you only an idea, the implementation should be yours:

• Initialize the global counter to zero.
• Sort the list starting with the smallest number.
• Create a list of integers (one entry per number with one index).
• Iterate through each number (index i) and do the following:
• Check the dividers at positions 0 to i-1.
• Save the number of delimiters in the list at position i.
• Extract the number of separators from the list for each separator and add each number to the global counter.
• If you are not finished, go to the third.
• Your result should be in the global counter.