The Python Oracle

Find maximum number of valid combinations for elements of two arrays

--------------------------------------------------
Hire the world's top talent on demand or became one of them at Toptal: https://topt.al/25cXVn
and get $2,000 discount on your first invoice
--------------------------------------------------

Take control of your privacy with Proton's trusted, Swiss-based, secure services.
Choose what you need and safeguard your digital life:
Mail: https://go.getproton.me/SH1CU
VPN: https://go.getproton.me/SH1DI
Password Manager: https://go.getproton.me/SH1DJ
Drive: https://go.getproton.me/SH1CT


Music by Eric Matyas
https://www.soundimage.org
Track title: RPG Blues Looping

--

Chapters
00:00 Find Maximum Number Of Valid Combinations For Elements Of Two Arrays
01:57 Answer 1 Score 0
02:22 Accepted Answer Score 3
02:49 Answer 3 Score 1
03:15 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