Ninja and his dessert.

Easy
0/40
Average time to solve is 10m
0 upvote
Asked in company
Facebook

Problem statement

Ninja is planning to make dessert. For which he is going to buy ingredients. There are ‘N’ base flavors and ‘M’ toppings. Ninja has a target that he will be needing an amount of ‘K’ for making the dessert.

For making dessert, there are some basic rules

1. There should be exactly one base flavor.
2. Toppings can be one or more or none.
3. There are at most two toppings of each type.

Ninja wants to make a dessert with a total cost as close to the target price as possible.

You will be given an array/list flavor of size N representing the cost of each base flavor and another array/list toppings of size 'M' representing the cost of each topping and the target price.

Your task is to help Ninja to find the closest possible cost of the dessert to the target price 'K'. If there are multiple answers, return the lower one.

Example

Let N = 2 , M = 2 , K = 10, FLAVOR = [1,7] , TOPPING = [3, 4] , K = 10

Here we can make a dessert with the base flavor of price 7 and adding 1 topping of price 3. Which will cost 7 + 3 = 10, which is exactly equal to k, so the closest possible price would be 10.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains an integer ‘N’ representing the number of base FALVOURS.

The second line of each test case contains ‘N’ integer representing the cost base FLAVOURS.

The third line of each test case contains an integer ‘M’ representing the number of TOPPINGS.

The second line of each test case contains ‘M’ integer representing the cost TOPPINGS.

The fifth and last line of each test case contains an integer ‘K’ representing the target price for dessert.
Output Format 
For each test case, print a single line containing a single integer denoting the closest possible price of the dessert to the target price.

The output of each test case will be printed in a separate line.

Note:

You don’t need to print anything or take input. It already has been taken care of. Just implement the function.
Constraints 
1 <= T <= 5
1 <= N, M <= 10
1 <= FLAVOUR[i] , TOPPINGS[i] <= 10 ^ 4
1 <= K <= 10 ^ 4 

Time limit: 1 sec.
Sample Input 1
2
2
1 7
3
1 2 3
10
1
10
3
5 6 11
9
Sample Output 1
10
10
Explanation
Test case 1

In this case, Ninja has 2 base flavours of cost 1 and 7,  and 3 toppings of price 1 and 2. Here target price is 10. So if Ninja takes a base of cost 7 and 1 topping of cost 3, then Ninja can make a dessert exactly of cost 10 ( 7 + 3), i.e., target price.

Test case 2

In this case, Ninja has only one base flavour of cost 10 and 3 toppings of 5, 6, 11. To make the dessert, Ninja must need a base, so 10 is the minimum cost that he must spend. Now, if he will add toppings price will rise further. So the closest possible price is 10.
Sample Input 2:
2
4
1 8 3 4
3
2 3 4
20
1
2
1
2
7
Sample Output 2:
20
6
Hint

As constraints are less, try all the possible combinations.

Approaches (1)
Backtracking Approach

 There are 3 ways to make a dessert

  1. Add one topping to flavor[i]
  2. Add two toppings to flavor[i]
  3. Don’t add any toppings to flavor[i]

Implement this with recursion since we have 3 choices at each instant.

We will now take a particular base flavor and start adding toppings to it in the above ways. 

 

Algorithm:

 

  • Function to choose the closest price to target.
    • int  closest(int a, int b, int target)
    • If a is 0, then return b or vice versa.
    • If the absolute value of (a - target) is equal to the absolute value of (b - target), then return smaller of a and b.
    • If the absolute value of (a - target) is greater than the absolute value of (b - target), then return b, else return a.
  • Function to find the closed value for a specific base flavor.
    • int dfs(int[] &topping, int index, int sum,int target)
      • If index >= topping size then return sum.
      • Initialize a variable ‘a’ to store the first way for a specific base. So a= dfs(topping,i + 1,sum + topping[i]).
      • Initialize a variable ‘b’ to store the second way for a specific base. So b = dfs(topping, i + 1, sum+ topping[i] * 2)
      • Initialize a variable ‘c’ to store the third way for a specific base. So c = dfs(topping, i + 1, sum);
      • Finally, return sum, where sum= closest(a, closest(b,c))
  • Function to find the closest price possible
    • int  closestCost(int[]flavor, int[]topping, int target)
      • Initialize a variable ans=0 to store answer.
      • Iterate i from 0 to base size - 1.
        1. Update ans as  ans= closest(dfs(topping, 0,  base[i]),ans)
      • Return ans.
Time Complexity

O(N * 3 ^ M), where N is the number of base flavors and M is the number of toppings.

 

For each base, you create 3 branches in the recursive tree where the tree is m levels deep (total toppings). So the complexity is O(N * 3 ^ M).

Space Complexity

O(M), where M is the number of toppings.

 

We are traversing at most M deep in the recursive tree, so the total space used is M.

Code Solution
(100% EXP penalty)
Ninja and his dessert.
Full screen
Console