What is wrong with this approach Sum and GCD

help
1

Hello everyone!
I have a query regarding the approach to solving Sum and GCD problem.
My approach was to solve by greedy approach by simply taking two sets let A and B.
And putting the first two elements in both sets.
Now for every ith element i>2 we have three choices.

1. Put in set A
2. put in set B
3 .merge set A and B make a new set For ith element.

Out of all three choices take the maximum

I tried every case I can think of but got the wrong answer. By another approach I got AC but I wonder where I was wrong.
Here is my submission link

3 Likes
2

My approach is same. Idk why it doesn’t work. I tried to prove the above method is either right or wrong but I couldn’t. Lets hope someone will prove it wrong and give a corresponding testcase.

By the way, what is the other approach you used?

4

It was quite clear that your answer is always going to be greater than ans>= max+1
where max is the maximum element in the array
So put the first and second maximum in set a and b find gcd of the rest and consider both cases of putting the value in set a and b.
take the maximum of both cases. Solution

2 Likes
5

Hey I used the similar greedy logic as yours, and got identical results. All except first 2 test cases of subtask 2 failing.
Can you give a test case where this logic fails?

6

As I mention I am also unable to find some test case where it fails.
Let’s hope someone will give some case.

1 Like
7

Your solution is like a dp solution, where it assumes an optimal substructure. But this is not the case here, there is no optimal substructure in the problem given.
And also your solution depends on the order of the elements, which will not likely give a correct solution.
After beating around for more than 1 hour, I found a test case where your solution fails:-

5
5 5 8 10 9
Interestingly, if you change the order of the elements it gives the correct result, here it is:-
5
5 5 8 9 10

1 Like
8

Yes you are right about it.Here don’t need to take care of ordered of the elements.
Thanks bro

1 Like
9

I presorted the array and applied the above logic. It still fails to pass all the testcases. Check my solution: solution

10

By sorting you are again taking the order of an element as an factor which we don’t need to take into account.
This approach is wrong…

1 Like
11

This solution will fail on N > 3, and where the optimal answer is choosing the second highest element and whose optimal answer for size N-1 is the highest element and the likes. I’m too lazy to find such a case, but if you will you may write a test generator for it.

1 Like