The Python Oracle

Find maximum number of valid combinations for elements of two arrays

Become part of the top 3% of the developers by applying to Toptal https://topt.al/25cXVn

--

Track title: CC B Schuberts Piano Sonata No 16 D

--

Chapters
00:00 Question
02:34 Accepted answer (Score 3)
03:08 Answer 2 (Score 1)
03:42 Answer 3 (Score 0)
04:11 Thank you

--

Full question
https://stackoverflow.com/questions/1752...

--

Content licensed under CC BY-SA
https://meta.stackexchange.com/help/lice...

--

Tags
#python #algorithm #python3x

#avk47


ACCEPTED ANSWER

Score 3


As far as I can tell, to solve this:

  • Construct bipartite graph G such that for each Ai and Bj, if GCD(Ai,Bj) > 1, there is an edge (Ai, Bj) in G.

  • Find the maximum matching of G

  • Cardinality of the matching is the solution

I don't see how this could be solved faster.



ANSWER 2

Score 1


I know where this problem you took. And you solution for this problem is wrong because its O(n^2) and greedy. n <= 10^5. 2 > a,b < 10^9 from array

I think in this problem you have to find some trick. And all algorithm for maximum matchings in bipartite graphs will TL.



ANSWER 3

Score 0


Assuming:

  1. Function is_coprime_pair(pair) is defined, accepts a list of length 2 and returns True for a pair of prime numbers
  2. a and b are iterables to combine 
    import itertools  
    not_coprimes = itertools.filterfalse(is_coprime_pair, itertools.product(a, b))

not_coprimes will hold all pairs that don't contain two prime numbers