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.