in this problem we need to find minimum energy required to destroy all the towers . i checked best submission it was using sum+=min(arr[a],arr[b]); can you please explain me why this greedy approach is correct .link to the solution
That greedy solution is perfect and there is no flaw. Since question is asking about minimum energy associated with that weight. So we will consider about minimum of value of any edge.
Why i am talking about edge? The reason is if we take out the minimum weight(lets call it A) of node then other node adjacent to that node(Call it B) will be removed. That means the node carrying higher weight would be removed, so all the edges connecting to that node B will automatically removed.
And that will be a plus point for our answer as we are going to reach the minimum of minimum weight automatically by just selecting the minimum weight associated to the edge.
I hope you will get this simpler language!
1 Like
it is taking minimum of both the values when input is given so suppose that (1,2) is given input suppose 1 is minimum we will include in the answer than suppose (1,3) is given suppose 3 is minimum we will include 3 in the answer last time we included 1 and now 3 its confusing me…i know its correct but i am asking about correctness proof of it…Thanks in advance