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
  • Joseph

    I would appreciate the explanation of this code. Could you just describe what are the steps?
    Thanks

    • I will explain the code with 2 examples. One that returns true and one that returns false.

      For the true one. I.e.: 50 an 100 – their factors are (5x5x2) and (5x5x2x2) therefore they have the same factors (not the same count of them but the set of those would be equal).

      If you are not familiar with GCD, please read how it is computed on Codility tutorial, I will assume you know what the method does.

      The GCD of 50 and 100 is 50.

      while (p != 1):

      p_gcd becomes 50 -> p becomes 1 -> we break and get into the else flow
      while (q != 1):
      q_gcd(100, 50) is 50 -> 100/50 = 2
      q_gcd(2,50) is 2 -> 2/2 = 1 -> break and get else
      -> return TRUE

      The false version i.e. 6(2×3) and 9(3×3)
      gcd(9,6) is 3

      while (p != 1):
      p_gcd(3, 6) becomes 3, for p 6/3 -> 2
      p_gcd(3, 2) -> 1, which breaks the loop and returns FALSE

      In other words, the remaining factors after gcd(p,q) must be the same as the factors of gcd. Which is true for 50 and 100 (gcd(50,100) is (5x5x2) and the remaining ones are 1 and 2). But not true for for 6 and 9 (gcd(6,9) is (3) and the remaining ones are 2 and 3.

      It is hard to explain… Please ask, if something is unclear. We might figure out a nice explanation 🙂