Find Maximum GCD sum without repetition in an array [closed]

Question

I have an array of even number of elements, I have to select n/2( n=array size), pairs and calculate their GCD such that the sum of their GCD is max, given once we use those elements from array, we cannot use them again.

Example1: `

Input : 8 24 12 16

Output : 20

Explanation: We select two pairs (8,16) and (12,24) as sum of their GCD is maximum. If we choose some other pairs, say (8,12) and (24,16), sum of their GCD will be 4+4 =8.

Example 2:

Input : 12 10 36 25 36 16

Output: 45

Explanation: We select the following 3 pairs : (36,36), (10,25) and (12,16) as the sum of their GCD is 36+5+4 = 45.

Our Approach:

for i in range(0,n):
   max = 0;
   for j in range(i+1,n):
      temp = gcd(a[i], a[j]) // standard func to find GCD 
      if(max<temp):
         store i and j
      store max gcd every time and finally make a[i] and a[j] =0 to mark the visited elements

Edited Constraint: max number of elements = 20, a[i]< 10^9.

Can you suggest an algorithm to optimally satisfy the above testcases in the least time complexity? Because my approach is failing on multiple testcases.

Answer 1

This is a comment but I am not allowed to post comment yet. It is not good to solve this problem by looking for the largest gcd. Take [8,9,24,36], the largest gcd is gcd(24,36) = 12, that will get you gcd(24,36) + gcd(8,9) = 12+1 =13. However, the largest sum is given by gcd(8,24) + gcd(9,36) = 8+9 = 17.