New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Connect Ropes

Contributed by

Himanshu Tanwar

Medium

0/80

Avg time to solve 25 mins

Success Rate 75 %

9 upvotes

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, Constraints, 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:

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:

Sample Output 2:

24
0

Auto

Console