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 as the minimum cost for connecting all the ropes.

Accepted Answer

Brute Force Approach

Clearly, the rope which is picked up first will be having its length included more than once in the final cost. If we pick a rope of larger length earlier, then we will be adding some extra cost to our final result.
So, the idea is to pick ropes of smaller lengths initially to minimize the impact on our final cost.

So, each time we will be finding two smallest ropes, connecting them and

adding the resulting rope back to the pile.

Space Complexity: O(1)Explanation:

O(1).

Constant space will be used.

Time Complexity: O(n^2)Explanation:

(N^2), where ‘N’ is the total number of ropes.

We will be finding the shortest two ropes at most ‘N’ times. So, overall time complexity will be O(N^2) as searching takes linear time.

Accepted Answer

Heap Approach

The idea is to use a Heap Data Structure which extracts minimum value in Log(N) time.

Here is the complete algorithm:

Create a min-heap from all the lengths of ropes.
Iterate till the number of elements in the min-heap is greater than one.
1. Extract the smallest two ropes from the min-heap
2. Connect these two extracted ropes and insert the new rope formed back into the min-heap.
3. Keep incrementing the ‘finalCost’ by the sum of lengths of the extracted ropes.
Return the ‘finalCost’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of ropes.

We will be creating a minHeap which will hold all the ‘N’ ropes initially. So, the space complexity will be linear.

Time Complexity: O(nlogn)Explanation:

(N *log N), where ‘N’ is the total number of ropes.

We will be finding the shortest two ropes at most ‘N’ times. So, overall time complexity will be O(N *logN) as searching will take logarithmic time for minHeap.

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 Gainsight Associate Software Engineer interview questions & answers

Popular interview questions of Associate Software Engineer