0

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!

Karan Singh
  • 553
  • 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? – lulu Jul 28 '19 at 12:26
  • @lulu yes it is. Sorry for the poor phrasing. I'll correct it. – Karan Singh Jul 28 '19 at 12:28
  • 1
    And please include the link to the programming contest. – lulu Jul 28 '19 at 12:28
  • do you know not to pair up primes or prime powers with different bases as a pair unless forced ? –  Jul 31 '19 at 21:01

0 Answers0