Codility ‘CommonPrimeDivisors’ Solution

Short Problem Definition:

Check whether two numbers have the same prime divisors.

Link

CommonPrimeDivisors

Complexity:

expected worst-case time complexity is O(Z*log(max(A)+max(B))2);

expected worst-case space complexity is O(1)

Execution:

I will post an explaining image soon!

Solution:
def gcd(p, q):
  if q == 0:
    return p
  return gcd(q, p % q)

def hasSameFactors(p, q):
    if p == q == 0:
        return True
    
    denom = gcd(p,q)
    
    while (p != 1):
        p_gcd = gcd(p,denom)
        if p_gcd == 1:
            break
        p /= p_gcd
    else:
        while (q != 1):
            q_gcd = gcd(q,denom)
            if q_gcd == 1:
                break
            q /= q_gcd
        else:
            return True
    
    return False


def solution(A, B):
    if len(A) != len(B):
        raise Exception("Invalid input")
    cnt = 0
    for idx in xrange(len(A)):
        if A[idx] < 0 or B[idx] < 0:
            raise Exception("Invalid value")
        if hasSameFactors(A[idx], B[idx]):
            cnt += 1
    
    return cnt

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin