Given $n$ positive integer and a positive integer k. How to find a subset of size k such that its elements 's gcd is maximal (just give the maximum value of gcd is okay).
Example: Give $3$ integers $1, 2, 4$ and $k = 2$; output: $2$ ($\gcd(2, 4) = 2$)
Could this problem be solved efficiently ? I am currently using randomized pruning search algorithm to find such value.
Edit: Since brute-force solution can have some overlap calculations, I am thinking about dynamic programming solution but I got stuck
Best Answer
there is no efficient solution. it reduces to the set cover problem, which is NP complete
so basically, you ask the question, "is it possible to come up with K numbers from this set such that their GCD is at least X" and then find the largest X for which this statement evaluates to true
essentially you are asking whether it is possible to choose some K sets (the factorizations of your list of numbers), such that the union of those sets contains every element in some other target set (the factorization of X)