'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Topics

Connect Ropes

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

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 )
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
Full screen
Console