There are 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. Find the minimum cost to connect all the ropes.
Examples
Input:arr = [4, 3, 2, 6]
Output:29
Connect 2 and 3 (cost 5). Array becomes [4, 6, 5]. Connect 4 and 5 (cost 9). Array becomes [9, 6]. Connect 9 and 6 (cost 15). Total cost: 5+9+15 = 29.
Constraints
• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^6
Complexity Analysis
Time
O(N log N) with Min-Heap, O(N^2) with array shifts.