Greedy Approach not working
Difference between en3 and en4, changed 76 character(s)
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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English CormoranStrike 2019-07-12 15:17:59 76
en3 English CormoranStrike 2019-07-12 15:16:44 1 Tiny change: 'Hi\nRecently' -> 'Hi,\nRecently'
en2 English CormoranStrike 2019-07-12 15:16:23 1
en1 English CormoranStrike 2019-07-12 15:15:37 1281 Initial revision (published)