How to find the number of pairs of non-coprimes in two given arrays in python?

Question

How to go about finding the number of non-coprimes in a given array? Suppose

a = [2, 5, 6, 7]
b = [4, 9, 10, 12]

Then the number of non-coprimes will be 3, since You can remove:

(2, 4)
(5, 10)
(6, 9)

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
count = 0
len_a = len(a)
len_b = len(b)
for i in range(len_a):
    for j in range(len_b):
        x = a[i]
        y = b[j]
        if(math.gcd(x,y) != 1):
            count += 1
print(count)

This is in reference to :https://www.hackerrank.com/challenges/computer-game/problem

I am receiving 8 as output.

Answer 1

If you are looking for the answer to be 3 in your example, I would assume you are counting the number of values in a that have at least one non-coprime in b.

If that is the case you could do it like this:

from math import gcd

def nonCoprimes(A,B):
    return sum(any(gcd(a,b)>1 for b in B) for a in A)

print(nonCoprimes([2,5,6,7],[4,9,10,12])) # 3

So, for each value in a check if there are any values of b that don't have a gcd of 1 with the value in a

Answer 2

Why do you expect the answer to be 3?
You're pairing 5 and 10, so you're obviously looking at pairs of elements from a and b disregarding their position.

Just print out the pairs and you'll see why you're getting 8...

import math
from itertools import product

a=[2, 5, 6, 7]
b=[4, 9, 10, 12] 
print(sum([math.gcd(x, y) != 1 for x, y in product(a, b)]))  # 8
print([(x, y) for x, y in product(a, b) if math.gcd(x, y) != 1])  # the pairs

---

Update: After reading the problem the OP is trying to handle, it's worth pointing out that the expect output (3) is the answer to a different question!
Not how many pairs of elements are not coprime, but rather how many non-coprime pairs can be removed without returning them into the arrays.
This question is actually an order of magnitude more difficult, and is not a matter of fixing one's code, but rather about giving the actual problem a lot of mathematical and algorithmic thought.

See some discussion here

---

Last edit, a sort-of solution, albeit an extremely inefficient one. The only point is to suggest some code that can help the OP understand the point of the original question, by seeing some form of solution, however low-quality or bad-runtime it is.

import math
from itertools import product, permutations

n = 4

def get_pairs_list_not_coprime_count(pairs_list):
    x, y = zip(*pairs_list)
    return min(i for i in range(n) if math.gcd(x[i], y[i]) == 1)  # number of pairs before hitting a coprime pair


a = [2, 5, 6, 7]
b = [4, 9, 10, 12]

a_perms = permutations(a)  # so that the pairing product with b includes all pairing options
b_perms = permutations(b)  # so that the pairing product with a includes all pairing options

pairing_options = product(a_perms, b_perms)  # pairs-off different orderings of a and b
actual_pairs = [zip(*p) for p in pairing_options]  # turn a pair of a&b orderings into number-pairs (for each of the orderings possible as realized by the product)

print(max(get_pairs_list_not_coprime_count(pairs_list) for pairs_list in actual_pairs))  # The most pairings managed over all possible options: 3 for this example

Answer 3

I believe the answer should be 8 itself. Out of the 4*4 possible combinations of numbers that you are comparing, there are 8 coprimes and 8 non-coprimes.

Here is an implementation of the code with the gcd function without using math and broadcasting to avoid multiple loops.

import numpy

a = '2 5 6 7'
b = '4 9 10 12'

a = np.array(list(map(int,a.split())))
b = np.array(list(map(int,b.split())))

def gcd(p,q):
    while q != 0:
        p, q = q, p%q
    return p

def is_coprime(x, y):
    return gcd(x, y) == 1

is_coprime_v = np.vectorize(is_coprime)
compare = is_coprime_v(a[:, None], b[None, :])

noncoprime_pairs = [(a[i],b[j]) for i,j in np.argwhere(~compare)]
coprime_pairs = [(a[i],b[j]) for i,j in np.argwhere(compare)]

print('non-coprime',noncoprime_pairs)
print('coprime',coprime_pairs)

non-coprime [(2, 4), (2, 10), (2, 12), (5, 10), (6, 4), (6, 9), (6, 10), (6, 12)]
coprime [(2, 9), (5, 4), (5, 9), (5, 12), (7, 4), (7, 9), (7, 10), (7, 12)]

Same solution but using the math.gcd() -

import math
import numpy

a = '2 5 6 7'
b = '4 9 10 12'

a = np.array(list(map(int,a.split())))
b = np.array(list(map(int,b.split())))

def f(x,y):
    return math.gcd(x, y) == 1

fv = np.vectorize(f)
compare = fv(a[:, None], b[None, :])

noncoprime_pairs = [(a[i],b[j]) for i,j in np.argwhere(~compare)]
print(noncoprime_pairs)

[(2, 4), (2, 10), (2, 12), (5, 10), (6, 4), (6, 9), (6, 10), (6, 12)]