Last Updated: 8 Apr, 2021

Ninja and his dessert.

Easy

Asked in company

Solve now

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.

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.

Solve now

Approaches

01 Approach

There are 3 ways to make a dessert

Add one topping to flavor[i]
Add two toppings to flavor[i]
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.

Solve now