The cheapest way to add them all up
Reported in interviews at (where)
You have a pile of whole numbers. In one step you take any two numbers out of the pile and put back their sum, and that step costs the sum. Keep going until one number is left.
For each pile, find the smallest total cost. A pile of one number costs nothing.
Input
The first line holds T, the number of tests. Each test is two lines: n, then the n whole numbers of the pile.
Output
For each test, one line: the smallest total cost for its pile.
- Input
3
4
4 3 2 6
1
7
3
5 5 5- Output
29
0
25
- 2 + 3 costs 5, then 4 + 5 costs 9, then 6 + 9 costs 15: 5 + 9 + 15 = 29.
- There is nothing to combine.
- Any two first cost 10, then 10 + 5 costs 15.
Limits
1 <= T <= 1001 <= n <= 100000the n of all the tests add up to at most 4000001 <= each number <= 10000
Hints
Hint 1
A number added early is paid for again in every later step it is part of, so the small numbers should be combined first.
Hint 2
Always combine the two smallest numbers in the pile. A min-heap hands them out in O(log n) each.
Where this was reported
- JPMorgan Chase, Code for Good interview, 2022 (GeeksforGeeks)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.