All problems

Minimum Cost to Connect Sticks

Medium · heap

You have a pile of wooden sticks, and sticks[i] is the length of stick i. You want to glue them all into one long stick.

In one step you pick any two sticks and glue them end to end. The new stick has the sum of their lengths, and the glue costs exactly that sum. The two sticks you used are gone and the new one joins the pile.

Keep going until one stick is left. Return the smallest total cost of doing this. If there is only one stick to begin with, no gluing is needed and the cost is 0.

Examples

Example 1

Input: sticks = [2, 3, 5]

Output: 15

Glue 2 and 3 for a cost of 5, leaving sticks of lengths 5 and 5. Glue those for a cost of 10. The total is 15.

Example 2

Input: sticks = [1, 1, 1, 1]

Output: 8

Glue two pairs of 1s for 2 each, then glue the two sticks of length 2 for 4. The total is 8.

Example 3

Input: sticks = [4]

Output: 0

There is only one stick already.

Constraints