Connect Ropes

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
10 upvotes
Asked in companies
Goldman SachsAmazonOYO

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4
4 3 2 6
3
1 1 8
Sample Output 1:
29
12
Explanation for Sample Input 1:
For test case 1
Optimal way to connect the ropes is:
Connecting 3 and 2 costs 5.
Ropes left  = [4,5,6]
Connecting 4 and 5 costs 9.
Ropes left = [9,6]
Connecting 9 and 6 costs 15.
One rope of length 15 is made.
Total cost for all the connections = 5 + 9 + 15 = 29.
Sample Input 2:
2
3
5 3 8
1
3
Sample Output 2:
24
0
Hint

Think greedily.

Approaches (3)
Greedy approach

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 :


 

  1. Sort the 'LENGTH' array.
  2. Pick the first two elements of the 'LENGTH' array, remove them from the array and push their sum in the 'LENGTH' array.
  3. 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.
  4. Return the value of 'MIN_COST'.
Time Complexity

O(N*(N*log(N))), Where N is the number of ropes.

 

The algorithm uses an inbuilt sorting algorithm to sort the array. So, for sorting time complexity will be N*log(N). The array is sorted until the size of the length array becomes 1. So, the final time complexity of the algorithm is O(N*(N*(log(N))).

Space Complexity

O(1)

 

Constant extra space is required.

Code Solution
(100% EXP penalty)
Connect Ropes
Full screen
Console