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

Question

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.

• greybeard: Given a plausible implementation of GCD (math, now), why are you searching for an LCM exhaustively?
• Peilonrayz: I'd look at two SO posts for GCD and LCM.
• Sidharth Samant: @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.

Answer 1

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.

• Gareth Rees: I would suggest writing docstrings for lcd and divisor_count.

Answer 2

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

• Alex: reduce might work faster than loop for that case, try it.