Array Reduction 1
Learn this problem
OracleFULLTIMEOAProblem statement
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
reductionCost(num: int[]) → int
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
Examples
Example 1
num = [4, 6, 8]return = 28Remove 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
num = [1, 2, 3]return = 9Make 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.
Constraints
2 ≤ n ≤ 10^40 ≤ num[i] ≤ 10^5