I am trying to solve a particular problem, where I have been given an array of integers and an integer X and I need to choose a subsequence of the array whose pairwise gcd is maximum given that the size of the subsequence must not exceed 2*X.

So for example, my array is [5, 7, 10, 8, 3, 4] and X is 2: the answer would be 9 since GCD(5, 10) + GCD(8, 4) = 9

The only approach I've been able to come up with was: At each step I'll find the maximum pairwise GCD of the numbers and then remove the 2 numbers from the array. Will keep adding it to a sum(which I have to output), under the constraints that I dont take in more than 2*X numbers.

  • 1
    $\begingroup$ Please edit the question to add a reference to that "particular problem". $\endgroup$ – John L. Jul 28 '19 at 15:16
  • $\begingroup$ It looks like that particular problem is part of live contest. If you created or discovered the problem on yourself, please introduce the background a bit. $\endgroup$ – John L. Jul 28 '19 at 15:50
  • $\begingroup$ What does the even in the title refer to? $\endgroup$ – greybeard Jul 28 '19 at 18:11
  • $\begingroup$ Something that irritates me: reading pairwise GCD, I picture all pairs. Tracing the example, I see pairs and fail to see subsequence. $\endgroup$ – greybeard Jul 28 '19 at 19:54
  • $\begingroup$ A simple example for which OP's algorithm fails could be $[40, 56, 5,7]$ and $X=2$. $g(40,56)+g(5,7)=8+1=9<g(40,5)+g(56,7)=12$ $\endgroup$ – John L. Jul 28 '19 at 20:35

Your Answer

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

Browse other questions tagged or ask your own question.