Minimum Cost of Reducing Array

Hard
0/120
Average time to solve is 15m
20 upvotes
Asked in companies
DunzoZSGrab

Problem statement

You are given an array 'ARR' consisting of 'N' positive integers, and you need to reduce the size of the array to 1 by performing an operation several number of times. In a single operation, you can merge any two adjacent elements of the array, and the cost of merging will be equal to the sum of those two elements. Find the minimum cost of reducing the given array by performing this operation several number of times.

In a single merge operation, the two elements are removed, and their sum is inserted at its place, hence decreasing the size of the array by 1 after each operation. For eg: Consider the array A1, A2, Ai-2, Ai-1, Ai, Aj, Aj+1, Aj+2 ,,,, An. Let the operation be performed on two indices i and j, So after merging the array will look like A1, A2, Ai-2, Ai-1, Ai+Aj, Aj+1, Aj+2,,,, An.

Note:

Note that the given operation will be performed only 'N'-1 times, where 'N' is the size of the given array.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer T denoting the number of test cases. 

The first line of each test case contains the integer N, denoting the size of the sorted array. 

The second line of each test case contains N space-separated integers denoting the array elements.
Output Format: 
The only line of output of each test case should contain a single integer which denotes the minimum cost of merging the whole array.
Constraints: 
1 <= T <= 50
1 <= N <= 100
1 <= ARR[i] <= 10^6

Time Limit: 1 sec
Sample Input 1:
1
3
1 3 7
Sample Output 1:
15
Explanation for Sample Input 1:
The optimal way of merging is as follows:
Merge (1, 3). The array becomes {4, 7}. Cost for this operation is 4.
Merge (4, 7). The array becomes {11}. Cost for this operation is 11.
Therefore the total cost of merging is 4 + 11 = 15.
Sample Input 2:
1
4
3 2 4 1
Sample Output 2:
20
Explanation for Sample Input 2:
The optimal way of merging is as follows:
1. Merge (3, 2), then array becomes {5, 4, 1}. Cost for this operation is 5. 
2. Merge (4, 1), then array becomes {5, 5}. Cost for this operation is 5.
3. Merge (5, 5), then array becomes {10}. Cost for this operation is 10.
Therefore the total cost of merging is 5 + 5 + 10 = 20.
Hint

Don’t try greedy.

Approaches (2)
Recursion with memoisation.
  • It can be proved that the greedy solution will not be optimum, so we need to solve this by dp or recursion. E.g., if ‘ARR’ = {6,4,4,6} and we try to merge the elements with minimum sum first, i.e. merge 4 and 4 first and so on, we will get the answer as 42, but the optimal merging gives 40.
  • The main idea is to merge two consecutive numbers at every possible index ‘i’ and then recursively call it for the left and the right parts.
  • As we know for an integer at index ‘i’, it has two choices: either to merge with element on its left or to merge with element on its right. Thus we can try all possibilities, and take the minimum.
  • To optimise recursion, we can memoize the results into a 2D array, so that we don’t have to recalculate the values for merging again and again.
  • Let the function name be MIN_COST() which will give the minimum cost of merging, where we assume that MIN_COST(i, j) returns the optimum cost for merging elements of the array from index i to index j. Now when trying to merge from i to j, we are assuming that we have already merged the elements from 1 to i, and j to ‘N’, where ‘N’ is the size of the array, and this is why dynamic programming comes into play.
  • Let us create a 2D array ‘DP[200][200]’, where ‘DP[L][R]’ will contain the minimum value of merging ‘ARR[L...R]’ into one.
  • Hence after the recursion is complete, our answer will be stored at ‘DP[1][N]’.
  • Let the array 'PREF_SUM' denote the prefix sum of the array ‘ARR’. So to find the sum of values from ‘ARR[L]’ to ‘ARR[R]', we can use ‘PREF_SUM[R]’ - ‘PREF_SUM[L - 1]’.
  • Let us assume that we have to find the minimum cost for merging elements from ‘ARR[L]’ to ‘ARR[j]’. So let initially ‘DP[i][j]’ = infinity( ‘INT_MAX’ in C++ etc.).
  • Clearly the sum of elements of the array from index ‘L’ to index ‘R’ = ‘PREF_SUM[R]’ - ‘PREF_SUM[L - 1]’.
  • Since we are using recursion, we can try all the possible mergings of adjacent elements, so for the interval l to r, the number of possible mergings are ('ARR[L]', ‘ARR[L + 1]’),  ('ARR[L + 1]', ‘ARR[L + 2]’), ('ARR[L + 2]', ‘ARR[L + 3]’).... ('ARR[R - 1]
  • , ‘ARR[R]’).
  • After trying all the possible mergings, we can take the minimum of all and move forward. For merging the interval ‘L’ to ‘R’ in ‘ARR’, the cost of that segment will be equal to the sum of that segment.
  • We can write ‘DP[L][R]' = min('PREF_SUM(L, L)' + ‘PREF_SUM(L + 1, R)’ + ‘DP[L][L]’ + ‘DP[L + 1][R]’, ‘PREF_SUM(L, L + 1)’ + ‘PREF_SUM(L + 2, R)’ + ‘DP[L][L + 1]’ + ‘DP[L + 2][R]’, …, ‘PREF_SUM(L, R – 1)’ + ‘PREF_SUM(R, R)’ + ‘DP[L][R – 1]’ + ‘DP[R][R]’)

         ‘DP[L][R]’ = S('L', ‘R’) + min('DP[L][L]' + ‘DP[L + 1][R]’, ‘DP[L][L + 1]’ + ‘DP[L + 2][R]’, …, ‘DP[L][R – 1]’ + ‘DP[R][R]’)

  • Simplifying the previous statement, for ‘K’ = i to ‘K' = j-1 we can do the following to find the minimum cost:
    • ‘DP[i][j]’ = min('DP[i][j]', MIN_COST(i, k) + MIN_COST(k + 1, j) + ‘SUM’), where ‘SUM’ = ‘PREF_SUM[R]' - ‘PREF_SUM[L - 1]’, for all ‘K’ from i to j-1.
Time Complexity

O(N^3), where N is the size of the array.

Iterate a loop ‘k', for ‘i*j’ depth so ‘i’ and ‘j’ can be ‘N’ is worst-case so our all-time will be ‘N*N*N = N^3’.

Space Complexity

O(N^2), where N is the size of the array.

Storing data in 2-d ‘DP’ matrix.

Code Solution
(100% EXP penalty)
Minimum Cost of Reducing Array
Full screen
Console