FastPrep

Description

Solutions

Find Total Cost

👩‍🎓 NEW GRAD📚RELATED PROBLEMS

Given an array arr of n integers, a sequence of n-1 operations must be performed on the array.

In each operation,

Remove the minimum and maximum elements from the current array and add their sum back to the array.

The cost of an operation, cost = ceil((minimum_element + maximum_element) / (maximum_element-minimum_element + 1)).

Find the total cost to reduce the array to a single element.

Example 1:

Input:  arr = [2, 3, 4, 5, 7]
Output: 8 
Explanation:
     
The possible sequence of operations are:
   

Choose 2 and 7, the cost = ceil((2 + 7) / (7 - 2 + 1)) = ceil(9 / 6) = 2.
Remove 2 and 7, append 9, arr = [3, 4, 5, 9], total_cost = 2.

Choose 3 and 9, the cost = ceil((3 + 9) / (9 - 3 + 1)) = ceil(12 / 7) = 2, arr = [4, 5, 12], total_cost = 2 + 2 = 4.
        
Choose 4 and 12, the cost = ceil((4 + 12) / (12 - 4 + 1)) = ceil(16 / 9) = 2, arr = [5, 16], total_cost = 4 + 2 = 6.
        
Choose 5 and 16, the cost = ceil((5 + 16) / (16 - 5 + 1)) = ceil(21 / 12) = 2, arr = [21], total_cost = 6 + 2 = 8.

  
Return the total cost, 8.

Constraints:

:)