CODEWITHSUNDEEP
algorithm
yoloy
yoloy

Reputation: 161

Maximum sum of gcd

There are two arrays with natural numbers. It is necessary to calculate the maximum sum of GCD, using permutations.

For example:

A = [1,3,5,7,9]
B = [15,20,30,40,50]

We can get the maximum sum of GCDs, for example, by the following mixing:

enter image description here

And the answer to this test will be 13. (3+3+5+1+1)

The length of the arrays is equal to N. And N can be from 1 to 200.

I tried to brute force all the combinations, but such a solution does not fit the timeline

Please tell me the algorithm for solving this problem.

The numbers from the array can be from 1 to 10^16.

Upvotes: 2

Views: 255

Answers (1)

Photon
Photon

Reputation: 2777

Here's my approach:

  1. First let's create a weighted bipartite graph, elements of array A will belong to left side, elements of array B - right side, and the weight of some edge a->b is gcd(a,b)

  2. Now problem is reduced to optimal assignment problem which can be solved with various well known ways like Min-Cost-Max-Flow, Hungarian algorithm, etc.

Upvotes: 4

Related Questions