Connect N Ropes With Minimum Cost

Easy

0/40

Average time to solve is 20m

Contributed by

42 upvotes

Asked in companies

Problem statement

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.

The test-data is such that the result will fit into a 32-bit integer.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

4
4 3 2 6

Sample Output 1:

Explanation:

1) If we first connect ropes of lengths 2 and 3, we will left with three ropes of lengths 4, 6 and 5.

2) Now then, if we connect ropes of lengths 4 and 5, we will left with two ropes of lengths 6 and 9.

3) Finally, we connect the remaining two ropes and all ropes are now connected.

Total cost for connecting all ropes in this way is 5 + 9 + 15 = 29  which is the optimized cost.
Now there are other ways also for connecting ropes. For example, if we connect 4 and 6 first (we get three ropes of lengths 3, 2 and 10), then connect 10 and 3 (we get two ropes of length 13 and 2). Finally we connect 13 and 2. Total cost in this way is 10 + 13 + 15 = 38 which is not the optimal cost

Sample Input 2:

5
1 2 3 4 5

Sample Output 2:

Hint 1

Hint 2

Think how many times a rope’s length is getting added to the final cost.

Approaches (2)

Approach 1

Approach 2

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.

Time Complexity

(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.

Space Complexity

O(1).

Constant space will be used.

(100% EXP penalty)

Connect N Ropes With Minimum Cost

Console