Minimum Cost To Connect Sticks

Moderate
0/80
Average time to solve is 15m
8 upvotes
Asked in companies
LinkedInPayPalWalmart

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3  
2 4 3
4
1 8 3 5
Sample Output 1:
14
30
Explanation For Sample Input 1:
For the first test case, 
We have sticks of length {2, 4, 3}. First, connect sticks of length 2 and 3 to form a stick of length 5 and which gives a cost of 5. Now we have two sticks of length 5 and 4 each. Now we will connect sticks of length 5 and 4 to form one complete stick of length 9 which gives a cost of 9 and a total cost is 5 + 9 = 14.

For the second test case, 
We have sticks of length {1, 8, 3, 5}. First, connect sticks of length 1 and 3 to form a stick of length 4 and which gives a cost of 4. Now we have sticks of length as {4, 8, 5}. Then connect sticks of length 4 and 5 to form a stick of length 9 and it gives a cost of 9. Now we have sticks of length as {9, 8}. Finally, connect the stick of length 8 and 9 which gives a cost of 17 and a total cost is 4 + 9 + 17= 30.
Sample Input 2:
2
3
2 9 7
2
10 9
Sample Output 2:
 27
 19
Hint

Can you solve this problem by finding two minimum lengths every time from the given lengths?

Approaches (1)
Min Heap

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:

  1. We will create a variable minCost initialized to 0.
  2. We will also create a min-heap.
  3. We will traverse over the array ARR and put each element in our heap.
  4. 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.
  5. Repeat the above step till the size of our heap is greater than 1.
Time Complexity

O(N*Log(N)), where ‘N’ is the total number of sticks.

 

Since we are traversing the array ‘ARR’ and inserting each element in the heap which will take O(Log(N)) time for insertion of each element giving a total time of O(N*Log(N)). Also, we are traversing the heap with ‘N’ elements and performing the pop operation which will take O(Log(N)) time giving a total time of O(N*Log(N)). Thus, overall time complexity will be O(N*Log(N)).

Space Complexity

O(N), where ‘N’ is the total number of the sticks.

 

Since ‘N’ elements are stored in the heap, therefore, giving a space complexity of O(N).

Code Solution
(100% EXP penalty)
Minimum Cost To Connect Sticks
Full screen
Console