Combine The Slimes

Hard
0/120
profile
Contributed by
16 upvotes
Asked in companies
AmazonMicrosoft

Problem statement

Steve has ’N’ slimes. Each slime has a size between 0 and 99. He wants to merge all these slimes into one by repeatedly mixing two adjacent slimes. The cost of mixing two slimes of size a and b is a * b, and the resulting slime has size (a + b) % 100. Help Steve compute the minimum cost to combine all slimes into one.

Help Steve to find the minimum cost in mixing for mixing all these slimes.

For Example : 
Slimes = {10, 7, 3}
On mixing slime 3 and 7 remaining slimes are: {10, 10} and the cost is 3 * 7 = 21.

On mixing slime 10 and 10 remaining slimes are: {10} and the cost of mixing is 10 * 10 = 100. 

So the final cost of mixing the slime is 121.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’ denoting the total number of slimes.

The next line contains 'n' integers denoting the size of the slimes.
Output Format : 
For each test case, print a single integer “ans” denoting the minimum cost of converting all these slime into one single slime.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 10    
1 <= N <= 100
0 <= slime[i] <= 99

Time limit: 1 sec
Sample Input 1 :
2
2
11 13
3
40 60 20
Sample Output 1 :
143
2400
Explanation For Sample Input 1 :
In the first test case, there are two slimes, Hence the answer is 11 * 13 = 143

In the second test case, we will first combine slime 1 and slime 2 which will result in slime 100 and 20, now the slime with size 100 will lose its size by 100. Now the slimes are 0 and 20 which will give the final answer 2400.
Sample Input 2 :
2
3
13 57 43
4
1 2 3 4
Sample Output 2 :
2451
35
Hint

Try to break the problem into subproblems starting with two slimes to n slimes.

Approaches (3)
Brute Force

In this approach, we will start combining every adjacent slime and check for the minimum possible cost.
 

The steps are as follows: 

  • In the “main” function:
    • Call the function recursion from start to end where start is the index of the first slime and end is the index of the last slime.
  • In the “recursion” function:
    • Check if the starting slime is greater than the ending slime, if true then return 0.
    • Else take a variable “ans” to store the minimum cost and iterate from the starting point(say i) to the ending point(say j) to find the minimum cost of combining the slime(say iterator be k):
      • The cost of combining slime i to j will be the minimum of “ans”, cost of combining the slime i to k + k to j + the total size of the slimes from i to k * k to j. i.e. “ans” = min(“ans”, “recursion(i, k)” + “recursion(k + 1, j)” + “computeSiz(i , k)” * “computeSiz(k + 1, j)”.
    • Return ans.
  • In the “computeSiz” function:
    • Take a variable ans in which we will store the final size of slimes from i to j.
    • Iterate through all the slimes from i to j:
      • Add all the slimes to “ans”
    • Return (“ans” % 100).
Time Complexity

O( 2 ^ N ), where N is the total number of slimes.

 

As we are checking for every possible case of combining the slimes.

Hence the time complexity is O( 2 ^ N ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Combine The Slimes
Full screen
Console