Connect N Ropes With Minimum Cost
You have been given 'N' ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.

Input format :

The first line of input contains an integer value 'N'. It denotes the total number of ropes. The second line of input contains 'N' single space separated integers representing length of each rope i.e. a1, a2, a3, ... an.

Output Format :

The only line of output will contain an integer, the minimum cost for connecting all the ropes.

Note:

You need not to print anything, it has been already taken care of. Just implement the given function.

Constraints :

1

Question

Connect N Ropes With Minimum Cost

You have been given 'N' ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.

Input format :

The first line of input contains an integer value 'N'. It denotes the total number of ropes.

The second line of input contains 'N' single space separated integers representing length of each rope i.e. a1, a2, a3, ... an.

Output Format :

The only line of output will contain an integer, the minimum cost for connecting all the ropes.

Note:

You need not to print anything, it has been already taken care of. Just implement the given function.

Constraints :

1 <= N <= 10^5
1 <= ai <= 10^9

Time Limit : 1 sec

Accepted Answer

The problem is to connect N ropes of different lengths into one rope with minimum cost.

Sort the array of rope lengths in ascending order.
Initialize a variable to keep track of the total cost.
While there are more than one rope remaining, take the two shortest ropes and connect them.
Add the cost of connecting the two ropes to the total cost.
Replace the two shortest ropes with the connected rope.
Repeat the above steps until only one rope remains.
Return the total cost.

You have been given 'N' ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.

Input format :

Output Format :

Note:

Constraints :

Top Goldman Sachs Software Engineer Intern interview questions & answers

Popular interview questions of Software Engineer Intern

Top HR questions asked in Goldman Sachs Software Engineer Intern