There is an array of n integers called num[]. The array can be reduced by 1 element by performing a move. Each move consists of the following three steps:
- Pick two different elements
num[i]andnum[j],i ≠j. - Remove the two selected elements from the array.
- Add the sum of the two selected elements to the end of the array.
Each move has a cost associated with it: the sum of the two elements removed from the array during the move. Calculate the minimum total cost of reducing the array to one element.
Function Description
Complete the function reductionCost in the editor below.
reductionCost has the following parameter(s):
int num[n]: an array of integers
Returns
int: the minimum total cost of reducing the input array to one element
Example 1:
Input: num = [4, 6, 8]
Output: 28
Explanation:Remove 4 and 6 in the first move at a cost of 4 + 6 = 10, and the resultant array is num' = [8,10]. Remove 8 and 10 in the second move at a cost of 8 + 10 = 18, and the resultant array is num'' = [18].
The total cost of reducing this array to one element using this sequence of moves is 10 + 18 = 28. This is just one set of possible moves. For instance, one could have started with 4 and 8. Then 4 + 8 = 12, num' = [6,12] 6 + 12 = 18, num'' = [18], cost 12 + 18 = 30.
Example 2:
Input: num = [1, 2, 3]
Output: 9
Explanation:Make the following moves to reduce the array num = [1, 2, 3]:
- Remove 1 and 2 at cost; 1 + 2 = 3, resulting in num' = [3, 3]
- Remove 3 and 3 at cost; 3 + 3 = 6, resulting in num'' = [6].
Sum up the cost of each reduction to get 3 + 6 = 9.
2 ≤ n ≤ 10^40 ≤ num[i] ≤ 10^5
input:
output: