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 obtain the maximum pairwise gcd from a subsequence of the array 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.

But this approach is too slow. If someone can suggest a faster approach, it would be great. Thanks!

  • $\begingroup$ This is not clear at all. You say you are trying to find a subsequence, but your final answer is $9$, which is not a subsequence. If you meant the subsequence $\{4,5,8,10\}$ then it is not clear how you came up with the number $9$. And...what is the source of this problem? It looks like the sort of thing that shows up in programming challenges...is it? $\endgroup$ – lulu Jul 28 at 12:26
  • $\begingroup$ @lulu yes it is. Sorry for the poor phrasing. I'll correct it. $\endgroup$ – Karan Singh Jul 28 at 12:28
  • 1
    $\begingroup$ And please include the link to the programming contest. $\endgroup$ – lulu Jul 28 at 12:28
  • $\begingroup$ do you know not to pair up primes or prime powers with different bases as a pair unless forced ? $\endgroup$ – Roddy MacPhee Jul 31 at 21:01

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.