Maximize the sum of GCDs (Greatest Common Divisors) of a bipartition?

user_11146188 0
Viewed 4571

Given an array of positive numbers. I want to split the array into 2 different subset(s) such that the sum of their gcd (greatest common divisor) is maximum.

Example array: {6,7,6,7}.

Answer: The two required subsets are: {6,6} and {7,7}; their respective gcd(s) are 6 and 7, their sum = 6+7=13; which is the maximum gcd summation possible.

Gcd: Gcd of {8,12} is {4} as 4 is the greatest number which divides 8 as well as 12.

Note: gcd(X)=X in case the subset contains only one element.

My approach: By brute-forcing, I find all possible sub-sequences of the array,then, I find the maximum sum, but this does not work if the input size is greater than 30 numbers. I am in search of a more efficient approach.

Extra(s): Maximum size of any input number is 10^9 , time limit:-1s seems good, size of input might be as huge as 10^5

greatest-common-divisor c++
1 Answers

I think this is actually an easy problem posing as a difficult one.

First, let's ignore the possibility of values appearing more than once. Obviously, it is best to put all copies of a value in the same set, since moving some of them elsewhere can only hurt the GCD (edit: unless there is only a single distinct value). So we'll assume all elements are distinct. Also, let M be the maximum value of any of the elements.

Think about this way: There's a trivial solution of taking the highest element on one side, and all the rest on the other. "All the rest" - may have a GCD of 1 (could be higher of course), so this solution gives you M+1.

Any subset of your inputs with more than a single distinct element cannot have a GCD higher than M/2 (since such a divisor has to be multiplied by another divisor, which is at least 2, to get to the original value, which is no higher than M). So edit: an optimal solution cannot be made up of two sets with multiple distinct element each. It must be one element vs all other elements.

Now consider the two highest elements, having values M and M-d for some d. If we choose neither of them to be the singleton, they're both in the large-group side, which means that group has GCD at most d (since if g|M and g|M-d then g|d); and the contribution of the singleton will be no more than M-d-1. So the overall score would be at most M-1 - that is, less than the score we get when choosing the highest value. It is therefore the case that either the highest or the second-highest (distinct) value in the input must be in a set of its own.

You must therefore need to do the following:

  • Handle the trivial case of only one distinct value.
  • Otherwise, obtain the 2 highest elements;.
  • Compute the GCD g_0 of all the n-2 lowest elements.
  • Compute the GCD's g_with_highest = GCD(g_0, M) and g_with_second_highest = GCD(g_0, M-d).
  • Choose the singleton by comparing M + g_with_second_highest with (M-d) + g_with_highest.
user_15930770
Related