Closest Cost

Moderate
0/80
Average time to solve is 34m
profile
Contributed by
14 upvotes
Asked in company
Google inc

Problem statement

Ninja is given the task to create a perfect gift for the king. He has ‘N’ wraps to choose from which he can choose to wrap the gifts. He also has ‘M’ gifts from which he can choose the gifts for the king. To choose the gifts, he sets some rules:

1) He must select exactly one wrapper to wrap all the chosen gifts.
2) He can select one or more gifts or no gifts at all.
3) He has 2 copies of the same gift. So, he can take 0 or 1 or 2 copies of each gift.

He also has a number ‘X’. He decided to spend in such a way that the total cost is as close as ‘X’. If there are multiple answers, print the minimum one.

For example:

Let’s say you have two wrappers with cost [1, 2] and three gifts with cost [3, 4, 5] and ‘X’ = 7. In the first case, you select wrapper number ‘2’ and gift number ‘1’ and ‘3’, so your total cost will be 2 + 3 + 5 = 10. While in the second case, you select wrapper number ‘1’ and gift number ‘2’, so your total cost will be 1 + 4 = 5. So out of both the cases, second case is closer to ‘X’ as abs(7 - 5) = 2 and abs(7 - 10) = 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format- 
First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains three space-separated integers, ‘N’, ‘M’ and ‘X’, denoting the number of the Wrappers, Gifts and closest number till you have to get the total cost, respectively.
The following line contains an array ‘W’ of ‘N’ space-separated integers, denoting the cost of the ‘ith’ wrapper.
The following line contains an array ‘G’ of ‘M’ space-separated integers, denoting the cost of the ‘ith’ gift.
Output Format- 
For each test case, print an integer denoting the total cost that is as close as ‘X’.
Constraints - 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10
1 <= ‘M’ <= 10
1 <= W[i], G[i] <= 10^4
1 <= ‘X’ <= 10^9

Time Limit: 1 sec
Sample Input-1
2
2 2 10
1 7
3 4
2 3 18
2 3
4 5 100
Sample Output-1
10
17
Explanation for Sample Input 1:
For test case 1:
    Choose wrapper number ‘2’ and one piece of gift number 1. Hence total cost will be 7 + 3 = 10.
For test case 2:
    Choose wrapper number ‘2’, one piece of gift number 1 and two pieces of gift number 2 . Hence total cost will be 3 + 4 + (2 * 5) = 17.
Sample Input -2
2
4 4 2
1 7 3 6 
1 7 3 6 
3 3 7
2 1 1
1 2 3
Sample Output -2
2
7
Hint

Enumerate all the possibilities.

Approaches (1)
Recursion

Approach: Let's say we have selected the ‘ith’ wrapper. Then we iterate in the gifts and try to select some gifts. There will be three ways to choose each gift. First, select one piece of that gift. Second, select two pieces of that gift, and lastly, do not select any piece of that gift. We can easily implement this with recursion since we have only three choices when selecting a particular gift. We will now take a particular wrapper and start choosing gifts following the above ways.


 

Algorithm:

  • Func recursion(i, cost, bestCost):
    • If (cost >= T) or ( i >= M).
      • If abs(X - cost) < abs(X - bestCost).
        • bestCost = cost.
      • Else if abs(X - cost) = abs(X - bestCost).
        • bestCost = min(bestCost, cost).
    • Else.
      • Add zero gift piece, call the function ‘recursion’ while updating the cost.
      • Add one gift piece, call the function ‘recursion’ while updating the cost.
      • Add two gift pieces, call the function ‘recursion’ while updating the cost.
  • Func Main().
    • Create a variable ‘ans’ and initialize it to ‘INT_MAX’.
    • For each wrapper.
      • Call the function ‘recursion’.
    • Print ‘ans’.
Time Complexity

O(N * 3^M). Where ‘N’ and ‘M’ are the numbers of wrappers and gifts.

For each wrapper, we have three ways to select each gift. Hence the overall complexity is O(N * 3^M).

Space Complexity

O(M). Where ‘M’ is the number of gifts. 

The recursion stack could go up to size ‘M’. Hence the overall complexity is O(M).

Code Solution
(100% EXP penalty)
Closest Cost
Full screen
Console