FastPrep
Problem · Heap

Reduce the Array (Also for DA)

Learn this problem
● MediumJCJPMorgan ChaseINTERNOA

Problem statement

Given an integer array, reduce the array to a single element.

In each operation, pick two indices i and j (where i ≠ j), and:

  • append the value of a[i] + a[j] to the array
  • delete a[i] and a[j] from the array

    • The cost of each operation is a[i] + a[j]. Find the minimum possible cost to reduce the array.

    Function

    minimizeCost(arr: int[]) → int

    Complete the function minimizeCost in the editor.

    minimizeCost has the following parameter:

    • int arr[n]: an array of integers

    Returns

    int: the minimum cost of reducing the array

    Examples

    Example 1

    arr = [25, 10, 20]return = 85

    Consider array [25,10,20].

    • Pick 10 and 20, cost = 10+20 = 30, array' = [25,30]
    • Pick 25 and 30, cost = 25+30 = 55, array" = [55]
    The cost is 30+55 = 85. This is the minimum possible cost.

    Constraints

    • 2 ≤ n ≤ 10^5
    • 1 ≤ arr[i] ≤ 100

    More JPMorgan Chase problems

    drafts saved locally
    public int minimizeCost(int[] arr) {
  // write your code here
}
    arr[25, 10, 20]
    expected85
    checking account