Food Festival

Moderate
0/80
Average time to solve is 27m
profile
Contributed by
1 upvote

Problem statement

Ninja is taking part in a food festival and he decided to prepare ‘N’ dishes with the spiciness of ith dish being ‘DISHES[i]’.

He has an unlimited supply of ‘N’ types of ingredients and the spiciness of ith type of ingredient is ‘INGREDIENTS[i]’.

The spiciness of a dish is defined as the sum of the spiciness of ingredients used in it.

Find the minimum number of ingredients needed to make all the dishes.

It is always possible to make every dish with the required spiciness from the combination of given ingredients.

Note: In the Problem Statement 1-based indexing is used and in the code 0-based indexing is used.

Example: 
Input: ‘N’= 4  ‘DISHES’ =[2, 4, 6, 8] ‘INGREDIENTS’=[1, 4, 5, 3]

Output: 7

First dish can be made using 2 ingredients of type 1. 
Second using 1 ingredient of type 2. 
Third using 2 ingredients of type 4. 
Fourth using 2 ingredients of type 2. 
So total 7 ingredients.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains one integer ‘N’ denoting the number of dishes and ingredients present.

The second line of each test case contains ‘N’ single space-separated integers, elements of the array ‘DISHES’.

The third line of each test case contains ‘N’ single space-separated integers, elements of the array ‘INGREDIENTS’.
Output format : 
For each test case, Return the minimum number of ingredients to make all dishes.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 500
1 <= N <= 500
1 <= DISHES[i] <= 1000
1 <= INGREDIENTS[i] <= 500  

Time Limit: 1 sec
Sample Input 1 :
2
3   
6 8 16
2 3 7
4
2 12 40 26
2 8 12 22
Sample Output 1 :
8
9
Explanation Of Sample Input 1 :
For the first case:
First dish can be made using 2 ingredients of type 2.
Second using 2 ingredients of type 2 and 1 ingredient of type 1.
Third dish using 2 ingredients of type 3 and 1 ingredient of type 1.
So total of 8 ingredients.

For the second case:
First dish can be made using 1 ingredient of type 1.
Second using 1 ingredient of type 3.
Third dish using 2 ingredients of type 2 and 2 ingredients of type 3.
Fourth dish using 1 ingredient of type 4 and 2 ingredients of type 1.
So a total of 9 ingredients.
Sample Input 2 :
2
8
20 98 66 32 16 128 200 168
2 2 2 4 5 50 4 19
6
6 8 16 34 189 155
1 1 1 3 5 9
Sample Output 2 :
38
54
Hint

Think of trying out all possible combinations of ingredients for each dish and add the one with minimum ingredients to the final answer.

Approaches (3)
Recursion

In this approach, we will recursively try out all possible combinations of ingredients for each dish. Function is called with ‘INDEX’ = 0 and ‘targetSpice‘ equal to spiciness of the dish then we have two options either to pick the ingredient of a given index or not pick.

 

In the case of pick, we have to again call the function with the same index (as we can have multiple ingredients of the same type) with target spiciness reduced by the spiciness of the ingredient.

 

In case of not pick, we have to call the function with index+1 and the same ‘targetSpice’.

If the value of ‘targetSpice’ becomes 0 after ‘INDEX’ reaches the end of the array then it is a valid combination.

 

The combination with the minimum total amount of ingredients is chosen. The same process is repeated for all the dishes.

 

The steps are as follows:-

// Recursive function to find minimum ingredients

function getMinIngredirentsUtil(int index, int targetSpice, [int]ingredients):

  1. If ‘INDEX’ is equal to size of the ‘INGREDIENTS’ array.
    • If ‘targetSpice’ is equal to 0 then return 0.
    • Else return 1e9.
  2. Initailze the variable ‘ANS’.
  3. Call the function getMinIngredirentsUtil with INDEX = INDEX+1 and same ‘targetSpice’ and store the returned value in ANS.
  4. If the value of targetSpice >= INGREDIENTS[INDEX]
    • Call the function getMinIngredirentsUtil with INDEX = INDEX and targetSpice = targetSpice-INGREDIENTS[i].
    • Update the value of ANS with min of ANS and value returned by the above function call.
  5. Return the value of ANS.


function getMinIngredients(int n, [int]dishes, [int]ingredients):

  1. Initialize a variable ‘ANS’ with 0, denoting the minimum ingredients needed to make all the dishes.
  2. Run a for loop from 0 to N-1
    • Call the function getMinIngredirentsUtil with INDEX=0 and ‘targetSpice’ = DISHES[i].
    • Add returned value to ‘ANS’
  3. Return the value of the variable 'ANS'.
Time Complexity

O( N * K * 2N ), Where ‘N’ is the size of the given array ‘INGREDIENTS’, ‘K’ is the maximum of no. of ingredients needed for each dish. 

 

We are trying all possible combinations of ingredients for each dish so its time complexity will be exponential and we are doing it for each dish so it will be multiplied by ‘N’.

 

Hence the time complexity is O( N * K * 2N ).

Space Complexity

O( K ), Where ‘K’ is the maximum of no. of ingredients needed for each dish.

 

Extra auxiliary space will be needed for the recursion call stack.

 

Hence space complexity is O( K ).

Code Solution
(100% EXP penalty)
Food Festival
Full screen
Console