3
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Given a plausible implementation of GCD (math, now), why are you searching for an LCM exhaustively? \$\endgroup\$ Commented Dec 13, 2016 at 23:39
  • 1
    \$\begingroup\$ I'd look at two SO posts for GCD and LCM. \$\endgroup\$ Commented Dec 14, 2016 at 0:43
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Dec 14, 2016 at 3:48

2 Answers 2

Reset to default
4
\$\begingroup\$
  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.

\$\endgroup\$
1
  • \$\begingroup\$ I would suggest writing docstrings for lcd and divisor_count. \$\endgroup\$ Commented Jan 10, 2017 at 21:41
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ reduce might work faster than loop for that case, try it. \$\endgroup\$ Commented Dec 14, 2016 at 9:04

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.