# sum and gcd june19 challenge!

Chef has a sequence of positive integers $$A_1,A_2, \dots, A_N$$. He wants to split this sequence into two non-empty (not necessarily contiguous) subsequences $$B$$ and $$C$$ such that $$\text{GCD}(B) + \text{GCD}(C)$$ is maximum possible. Help him find this maximum value.

Example case 1: For example, the sequence $$A=(4,4,7,6)$$ can be divided into subsequences $$B=(4,4,6)$$ and $$C=(7)$$.

But how the output comes out to be 9 As gcd of 7 is 1 itself.

• Is the question here to do with how the example case works? – hexomino Jun 22 '19 at 20:22
• In that case, GCD of a single integer is the integer itself, thus $GCD(7)=7$ ... – athin Jun 22 '19 at 22:38
• @athin has it right. Note that the definition of GCD given is "the largest positive integer that divides each element of this sequence," which does not necessarily imply the output is smaller than the inputs. – RShields Jun 23 '19 at 14:44

Example case 1:** For example, the sequence $$A=(4,4,7,6)$$ can be divided into subsequences $$B=(4,4,6)$$ and $$C=(7)$$.

GCD(B) = 2
GCD(C) = 7
GCD(B) + GCD(C) = 2 + 7 = 9

I have solved this question. Basically you have to do a couple of steps.

1. Use a set to store all distinct elements;

2. Sort them // Set in C++14 already sorts it.

3. Compute two cases

1. GCD(Largest) + GCD(All the rest);

2. GCD(Second Largest) + GCD(All the Rest)

4. Pick the max among them

• This may be the solution to the puzzle hosted at codechef. However, it is not an answer to the question that was asked. – LeppyR64 Jun 25 '19 at 16:07