A technician has n fiber-optic segments with given positive integer lengths. Splicing two segments of lengths a and b costs a + b and produces a single segment of length a + b. Splicing continues until a single segment remains. You may choose the order of splices freely.
Report the minimum possible total splice cost. If there is only one segment to begin with, no splicing is needed and the cost is 0.
Line 1: an integer n.
Line 2: n space-separated positive integers, the segment lengths.
A single integer: the minimum total splice cost.
Example 1
Input
3 1 2 3
Expected
9
Explanation
Splice 1 and 2 for cost 3 (segment 3), then splice 3 and 3 for cost 6. Total 9, which is the minimum over all orders.
Example 2
Input
1 5
Expected
0
Explanation
Only one segment, so no splicing is needed and the total cost is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →