2
$\begingroup$

Can anyone please help me out with the https://www.codechef.com/JUNE19B/problems/SUMAGCD question?

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.

|improve this question
$\endgroup$
  • $\begingroup$ Is the question here to do with how the example case works? $\endgroup$ – hexomino Jun 22 '19 at 20:22
  • 2
    $\begingroup$ In that case, GCD of a single integer is the integer itself, thus $GCD(7)=7$ ... $\endgroup$ – athin Jun 22 '19 at 22:38
  • 1
    $\begingroup$ @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. $\endgroup$ – RShields Jun 23 '19 at 14:44
2
$\begingroup$

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

|improve this answer
$\endgroup$
-1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.