Last Updated: 7 Apr, 2021
Minimum Cost To Connect Sticks
Moderate
Asked in companies
You are given an array/list ‘ARR’ of ‘N’ positive integers where each element describes the length of the stick. You have to connect all sticks into one. At a time, you can join any two sticks by paying a cost of ‘X’ and ‘Y’ where ‘X’ is the length of the first stick and ‘Y’ is the length of the second stick and the new stick we get will have a length equal to (X+Y). You have to find the minimum cost to connect all the sticks into one.
Input format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains an integer ‘N’, representing the total number of sticks.
The second line of each test case contains ‘N’ space-separated integers denoting the length of each stick.
Output format:
For each test case, print the minimum cost to connect all the sticks into one by performing the above-mentioned operation.
Output for each test case is printed on a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^4
1 <= Val <= 5*10^3
Where ‘T’ represents the number of test cases, ‘N’ represents the number of sticks, and ‘Val’ represents the initial length of any stick.
Time Limit: 1 sec
Approaches
Approach:
- It is a greedy approach where we will form a min-heap of all the lengths of sticks that are given to us.
- In this approach, we will always find two sticks with minimum length and connect them and add their cost to our answer. Also, we will add the newly formed stick back into our min-heap. And then we will continue to do the same procedure for all the remaining sticks.
- Since we need to minimize the cost to connect all the sticks into one, therefore we have to greedily pick the two smallest lengths of sticks from given lengths and add them to the answer and continue it until we are left with one stick in our heap.
- We are picking the two smallest sticks every time because the new stick formed will also be added to our cost later. Therefore picking smaller sticks will reduce the total cost than using longer sticks which will increase the cost.
Algorithm:
- We will create a variable minCost initialized to 0.
- We will also create a min-heap.
- We will traverse over the array ARR and put each element in our heap.
- Now we will extract two top elements from the min-heap. Let the extracted elements be firstMinimum and secondMinimum. Add firstMinimum and secondMinimum and add their result in our minCost variable and also back in our heap.
- Repeat the above step till the size of our heap is greater than 1.