Hi, Recently i was solving a problem on codechef related to GCD (https://www.codechef.com/JUNE19A/problems/SUMAGCD). I developed an algorithm using Greedy Approach as follows: I created two placeholders, x and y, for the final result to be obtained. Since we have to bifurcate the numbers into sets, for which x will represent the GCD of all elements in set 1 and similarly y will represent the GCD of all elements in set 2. Now as per the question statement, any number can be in set 1 or set 2. My approach is to traverse the array linearly and for every element, try the following three possibilities: Let the element by J: Case 1: J is attached to set 1 and set 2 remains as it is. Let the new GCD of two sets be X1 and Y1. Case 2: J is attached to set 2 and set 1 remain as it is. Let the new GCD be X2 and Y2. Case 3: We concatenate set 1 and set 2 and replace it with set 1 and create new set 2 with only J in it. Let the new GCD be X3, and Y3. Now of all the three cases, we choose the case with the highest sum. At the end of the traversal, we should have the result with the maximum sum.

Refer to the code — (https://www.codechef.com/viewsolution/24658264)

But this approach is giving an incorrect answer for one of the subtest.

Can anyone point out the flaw in this approach? Thanks in advance.