# Time limit exceeded on finding out the GCD and LCM of a Python list

I'm doing this HackerRank problem:

Consider two sets of positive integers, $A=\{a_0, a_1, \ldots, a_{n-1}\}$ and $B=\{b_0, b_1, \ldots, b_{m-1}\}$. We say that a positive integer, $x$, is between sets $A$ and $B$ if the following conditions are satisfied:

1. All elements in $A$ are factors of $x$.
2. $x$ is a factor of all elements in $B$.

Given $A$ and $B$, find and print the number of integers (i.e., possible $x$'s) that are between the two sets.

Assuming lists a and b as in the problem, the main idea is finding the LCM of list a and the GCD of list b, and then finding out how many multiples of the LCM divide the GCD perfectly without remainders. I ended up with this -

from fractions import gcd

def lcm(a, b):
for i in xrange(max(a,b), a*b+1):
if i%a==0 and i%b==0:
l = i
break
return l

def count(l, g):
count = 1
if l==g:
return count
elif g%l !=0 and l%g != 0:
return 0
elif l<g:
for i in xrange(l, g, l):
if g%i==0:
count += 1
return count
else:
for i in xrange(g, l, g):
if l%i==0:
count +=1
return count

if __name__ == '__main__':
n,m = raw_input().strip().split(' ')
n,m = [int(n),int(m)]
a = map(int,raw_input().strip().split(' '))
b = map(int,raw_input().strip().split(' '))
l = reduce(lcm, a)
g = reduce(gcd, b)
print count(l, g)


But I pass only 7 of the 8 test cases, the last one getting terminated due to time out. I don't understand which part of my code would result in a long loop that might end up in a timeout.

P.S. I would also be very glad if any of you could point out any other inefficiencies or styling conventions in my code.

• Given a plausible implementation of GCD (math, now), why are you searching for an LCM exhaustively? – greybeard Dec 13 '16 at 23:39
• I'd look at two SO posts for GCD and LCM. – Peilonrayz Dec 14 '16 at 0:43
• @Peilonrayz, thanks for that link. I think the method shown is more streamlined than mine but I still get the timeout for that particular test case. – Sidharth Samant Dec 14 '16 at 3:48

## 2 Answers

1. It is a really bad idea to use a variable named l. I is hard to distinguish it from 1.
2. All these functions using xrange are inefficient

the lcd function can be efficiently calculated by

from fractions import gcd
def lcd(a,b):
return(a*b/gcd(a,b))


the count function is

count(l,g)=divisor_count(g/l)


where divisor_count is the number-of-divisors function

If the number n has the prime factor decomposition

$$n=p_1^{e_1}\cdot p_2^{e_2}\cdots p_k^{e_k}$$ then we have

$$\text{divisor_count}(n)=(e_1+1)\cdot(e_2+1)\cdots(e_k+1)$$

This can be calculated in the following way:

def divisor_count(n):
cnt=1
i=2
while i*i<=n:
e=0
while n%i==0:
n//=i
e+=1
cnt*=e+1
i+=1
if n>1:
cnt*=2
return(cnt)


This divisor_count function runs in $$O(\sqrt{n})$$ time, the xrange implementation uses $$O(n)$$ time.

• I would suggest writing docstrings for lcd and divisor_count. – Gareth Rees Jan 10 '17 at 21:41

It turns out my count function was inefficient. Going through the discussion forms on the site, I found this which passed all the test cases -

def count(l, g):
count = 0
for i in xrange(l, g + 1, l):
if g%i == 0:
count += 1
return count

• reduce might work faster than loop for that case, try it. – Alex Dec 14 '16 at 9:04