you are given an array of triplets of size N, we have to choose one number from each triplet, forming a new array of N size, such that the GCD of the numbers in the new array is maximum.
example: an array of triplets where N=3 -
[(70, 105, 42),
(35, 60, 210),
(36, 70, 420)]
so if we choose 105 from first element, 210 from second and 420 from third, we get a GCD of 105. which is the maximum possible answer.
when I used brute force, I got time limit exceeded (since there are exponential possibilities to check). I couldn't think of a way to use dynamic programming here, and apart from that I am unsure how to proceed with this question.
I think you can maintain a list of possible gcds. If the first triple is (a0, a1, a2), you start with set(a0, a1, a2). Then for the second triple (b0, b1, b2) you take the gcd of each element with every element of your set. So: (gcd(a0, b0), gcd(a0, b1), gcd(a0, b2), gcd(a1, b0), gcd(a1, b1), gcd(a1, b2), gcd(a2, b0), gcd(a2, b1), gcd(a2, b2)). And so on.
At each step, you could remove any element in your set that's a factor of any other. (It's probably not worthwhile to do this though).
Once you've processed every triple, the largest value in your set is your answer.
It looks like this set might grow exponentially, but it's bounded by a function of K (the maximum value in any triple in the array): the number of elements in your set can never be larger than the number of factors of all three elements in any triple, which is o(K^eps) for all eps>0, and in practice will be smaller. For example, if all of your numbers are less than 1 billion, the set will never be larger than 4032 (the largest number of factors of any number less than 1 billion is 1344, and 4032 = 3*1344).
That means this algorithm does O(NK^eps) gcd operations for all eps>0.