Merging Stones

Ninja
0/200
Average time to solve is 27m
profile
Contributed by
10 upvotes
Asked in company
Codenation

Problem statement

You are given an array of piles of stones ‘stones’, where ‘stones[i]’ represents the number of stones in ‘ith’ piles. You are also given an integer ‘K’. Your task is to merge stones into one pile with minimum cost. In one operation you can take exactly ‘K’ consecutive piles and merge them and the cost of merging piles of stones in a particular operation is the total number of stones in all piles considered in that operation.

If it is not possible to merge, return -1.

For example: 
You are given ‘stones’ = [4, 3, 4, 2, 5] and ‘K’ = 3, Here one way you can first merge [3, 4, 2] with a cost of 9, to form the array [4, 9, 5] then merge these piles as [18], with a cost of 18. The total cost to merge the array is 27, which is the minimum of all the possible ways. Hence the answer is 27.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘K’, representing the number of piles and ‘K’ the integer given.

The second line of each test case contains ‘N’ space-separated integers, representing the elements of the array ‘stones’.
Output Format: 
For each test case print a single integer representing the minimum cost to merge the whole array into 1.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= |N| <= 10^2
2 <= K <= N
1 <= |stones| <= 10^5

Time Limit: 1 sec.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1:
2
5 3
4 3 4 2 5
3 2
1 2 3
Sample Output 2:
27
9
Explanation:
For the first test case, ‘stones’ = [4, 3, 4, 2, 5] and ‘K’ = 3, Here one way you can first merge [3, 4, 2] with a cost of 9, to form the array [4, 9, 5] then merge these piles as [18], with a cost of 18. The total cost to merge the array comes 27, which is the minimum. Hence the answer is 27.

For the second test case, ‘stones’ = [1, 2, 3] and ‘K’ = 2, Here is one way you can first merge [1, 2] with a cost of 3, to form the array [3, 3], then merge these piles [6], with a cost of 6. The total cost to merge the array comes 3 + 6 = 9, which is the minimum. Hence the answer is 9.
Sample Input 2:
2
3 3
5 8 9
5 4
4 5 3 2 3
Sample Output 2
22
-1
Hint

Try to find a recursive solution

Approaches (3)
Recursive approach

In this approach, we will look at all possible subarrays of the array, for any array, we will have to add the sum of its elements to the solution at one point or another. If the subarray has only ‘K’ elements we will return the sum of all elements otherwise we will further check if more piles can be formed in the subarray or not and return the minimum of all possible solutions.

 

Since for each subarray, we will require the sum of its element we will create a prefix sum array to get the subarray sum in O(1) time.
 

We will create a recursive function mergeStonesRecur(stones, preArr, k , start, end), where start and end are the starting and ending indices of the current subarray, while preArr is the prefix sum array of stones.

 

Algorithm:

  • In the function mergeStoneRecur(stones, preArr, k, start, end)
    • If start is equal to end return 0
    • If end - start + 1 is equal to k return preArr[end + 1] - preArr[start]
    • Set minSol as infinity
    • Iterate i from start to end at each step increment i by k - 1
      • Set firstPile as mergeStoneRecur(stones, preArr, k, start, i)
      • Set otherPiles as mergeStonesRecur(stones, preArr, k, i + 1, end)
      • Set mergingCost as 0 if end - start is divisible by k - 1, otherwise set it as preArr[end + 1] - preArr[start]
      • Set minSol as minimum of itself and firstPile + otherPile + mergingCost
    • Return minSol
  • In the given function
    • Create a prefix sum array preArr from the array stones
    • Return mergeStoneRecur(stones, preArr, k, 0, size of stones - 1)
Time Complexity

O(N^N), Where N is the size of the array

 

At each function call, we are calling the function N times. Hence the overall time complexity is O(N^N).

Space Complexity

O(N), Where N is the size of the array

 

The space complexity of the recursion stack is O(N).

Code Solution
(100% EXP penalty)
Merging Stones
Full screen
Console