Mixtures

Hard
0/120
Average time to solve is 50m
profile
Contributed by
4 upvotes
Asked in company
Salesforce

Problem statement

Hermione is attending the Magic Potion's Class in Hogwarts. She has ‘N’ potions in front of her lying in a row. Her task is to combine these potions into 1. To do so, she can pick any two adjacent potions of color ‘A’, ‘B’ and mix them to form another potion of color ‘C’=(‘A’ + ‘B’)%100, which will then replace ‘A’ and ‘B’ in the row (Two potions combine to form one potion). But when a new potion is formed, it produces smoke of value ‘A’ * ‘B’. Hermione needs your help to minimize the smoke produced in the above task.

For example:

For the given array [ 1, 3, 1, 2, 4 ].

The optimal way will be:

Mix the last two elements. The array will be [1, 3, 1, 6 ], and the smoke will be 8.
Mix the first two elements. The array will be [4, 1, 6 ], and the smoke will be 11.
Mix the last two elements. The array will be [4, 7], and the smoke will be 17.
Mix the remaining two elements. The array will be [11], and the smoke will be 45.

So, the output will be 45.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’, representing the number of potions.

The second line of each test case contains ‘N’ space-separated integers representing the color value of the potions.
Output Format: 
For each test case, print a single-digit integer representing the minimum amount of smoke generated.

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 <= X <= 99

Where ‘X’ is the color value of a potion.

It is guaranteed that the sum of ‘N’ over all test cases doesn’t exceed 100.

Time Limit: 1 sec.
Sample Input 1:
2
4
3 7 10 5
6
1 2 3 4 5 6
Sample Output 1:
221
175
Explanation for Sample Output 1:
Test Case 1:
For the given array [ 3, 7, 10, 5 ].

The optimal way will be:

Mix the middle two elements. The array will be [3, 17, 5 ], and the smoke will be 70.
Mix the last two elements. The array will be [3, 22 ], and the smoke will be 155.
Mix the remaining two elements. The array will be [ 25 ], and the smoke will be 221.

So, the output will be 221.


Test Case 2:

For the given array [ 1, 2, 3, 4, 5, 6 ].

The optimal way will be:

Mix the last two elements. The array will be [1, 2, 3, 4, 11 ], and the smoke will be 30.
Mix the last two elements. The array will be [1, 2, 3, 15 ], and the smoke will be 74.
Mix the last two elements. The array will be [1, 2, 18 ], and the smoke will be 119.
Mix the last two elements. The array will be [1, 20 ], and the smoke will be 155.
Mix the remaining two elements. The array will be [ 21 ], and the smoke will be 175.

So, the output will be 175.
Sample Input 2:
2
6
10 24 16 25 37 49
5
37 25 1 27 3
Sample Output 2:
4397
2958
Hint

Can we use a recursive function to calculate the minimum smoke produced?

Approaches (3)
Recursion

We will implement a recursive function, which will take two indices ‘X’ and ‘Y’ as arguments and return the minimum smoke produced by merging all the potions between these two indices. To find this we will iterate from ‘X’ to ‘Y’ and will find the optimal adjacent indices which we should mix to get minimum smoke.

So, for the final output, we will give zero and ‘N - 1’ as the argument and the function will return the optimal answer.

 

Algorithm:

 

  1. We will implement a prefix sum array ‘PREF’ to calculate the prefix sum mod 100.
  2. Then we will call the ‘solver’ function with zero and ‘N-1’ as arguments.
  3. If ‘X’ == ‘Y’, the smoke produced will be zero since there is only one potion.
  4. Else we will iterate from ‘X’ to ‘Y-1’ and will choose the adjacent indices which we should mix to produce minimum smoke.
  5. For two adjacent indices, ‘i’ and 'i + 1’, the smoke produced will be the sum of the smoke produced from ‘X’ to ‘i’, smoke produced from ‘i + 1’ to ‘Y’, and the product of the sums of ‘X’ to ‘i’ and ‘i + 1’ to ‘Y’.
  6. Finally, we will take the minimum smoke from all the possible values and then return it.
Time Complexity

O(N!) , where ‘N’ is the size of the array.

 

At each step, we are mixing two potions and reducing the number of potions by 1.

So the final complexity will be N*(N-1)*(N-2)....., which is O(N!).

Space Complexity

O(N), where ‘N’ is the size of the array.

 

We will use a prefix sum array. So the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Mixtures
Full screen
Console