4
\$\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\$
  • 1
    \$\begingroup\$ Given a plausible implementation of GCD (math, now), why are you searching for an LCM exhaustively? \$\endgroup\$ – greybeard Dec 13 '16 at 23:39
  • 1
    \$\begingroup\$ I'd look at two SO posts for GCD and LCM. \$\endgroup\$ – Peilonrayz Dec 14 '16 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\$ – Sidharth Samant Dec 14 '16 at 3:48
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\$
  • \$\begingroup\$ I would suggest writing docstrings for lcd and divisor_count. \$\endgroup\$ – Gareth Rees Jan 10 '17 at 21:41
2
\$\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\$
  • \$\begingroup\$ reduce might work faster than loop for that case, try it. \$\endgroup\$ – Alex Dec 14 '16 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.