Last Updated: 9 Dec, 2020
Connect Ropes
Moderate
Asked in companies
Given a number of ropes say ‘N’ and an array of integers of size ‘N’ containing the length of ropes. Your task is to connect the ropes into one. The cost to connect two ropes is equal to the sum of their lengths. Find the minimum cost for connecting all the ropes.
Input Format:
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow.
The first line of each test case contains the number of ropes.
The second line of each test case contains space-separated integers containing the length of ropes.
Output Format:
For each test case, print the minimum cost to connect all the ropes. Each value is separated by a single space.
The output of each test case is printed in 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 <= length[i] <= 10^4
Where 'length[i]' is the length of the 'i-th' rope.
Time Limit: 1 sec
Approaches
When closely observed, it can be seen that the ropes which are connected first add up to the total cost more number of times than the ones which are connected later. So, to reduce this cost, that is being added again and again, shorter ropes are connected first moving on to longer ones.
Below is the algorithm :
- Sort the 'LENGTH' array.
- Pick the first two elements of the 'LENGTH' array, remove them from the array and push their sum in the 'LENGTH' array.
- Repeat above two steps until the size of the 'LENGTH' array is greater than 1 and maintain a variable 'MIN_COST' and add the values of all the addition costs in it.
- Return the value of 'MIN_COST'.
The idea is the same as the previous approach but to find the two smallest values from the length array, for that, we use two variables. Then replace one of those values with the sum of them and another with INF. Maintain a variable 'MIN_COST' and keep on adding the cost of connecting ropes in 'MIN_COST'. Repeat the same process until all the ropes are connected.
Below is the algorithm:
- Take two variables to store the two minimum values.
- Replace one of the values with the sum of the two values found in step (1) and another with INF. Maintain a variable 'MIN_COST' and add all the costs of connections in 'MIN_COST'.
- Repeat the above two steps for ‘N’ - 1 times, that is until all the ropes are connected.
- Return the value of 'MIN_COST'.
The idea is the same as discussed in the previous approach, but can the same idea be implemented in a better way. Think of a data structure that can give us the minimum value in a time that is less than sorting it again and again. Min-Heap is one such data structure whose root gives the minimum value in constant time. In addition to any new element in the heap, heapify function takes place and takes logarithmic time.
Below is the algorithm :
- Take a min-heap. Initially push all the elements of the ‘LENGTH’ array in the heap.
- Remove the top two elements from the heap and add them and push their addition back into the heap.
- Repeat the above two steps until the size of the heap is greater than 1.
During every addition, add the value of adding in a variable say ‘MIN_COST’. - Return the value of ‘MIN_COST’.