Minimum Cost to Buy Rice

Moderate
0/80
profile
Contributed by
2 upvotes
Asked in company
Adobe

Problem statement

It’s year-end and also the perfect time to have a Ninja gathering. You are planning to invite your Ninja friends for a delightful rice meal.

The town you live in has exactly ‘N’ shops selling rice. The shops are numbered from 1, 2, 3 … N, and the i’th shop sells rice bags that weigh exactly i kgs. Each shop has an unlimited supply of the bags that they sell so you don’t have to worry about that. You are also given an array ‘COST’ where COST[i] denotes the price at which the i’th shop sells one bag of rice. Note that if COST[i] is equal to -1, then it means that the i’th shop is closed and you cannot buy rice from that shop (The array ‘COST’ follows 0-based indexing).

You have to buy exactly ‘W’ kgs of rice, you are not willing to buy extra rice to avoid any wastage. Find the minimum cost to complete this task, if it is not possible to complete the task then print “-1”.

Example : 
If ‘N’ = 5, ‘W‘ = 4 and “COST’’ = {100, 5, -1, 100, 100}.

Then, we can buy two bags of rice from the 2’nd shop. This shop sells rice in packing of 2kgs each and sells each bag for COST[1] = 5. Therefore we have to pay a total cost of 2 * 5 = 10 to complete this task.
Note that there are more ways to complete this task. For example, we can buy four bags of rice from the 1’st shop, this will have a cost of 4 * COST[0] = 400 which is much greater than the cost of 10 calculated earlier. Therefore we will print 10.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains two integers ‘N’ and ‘W’, denoting the number of shops and the weight of rice respectively.

The next lines contain N integers ‘COST’, denoting the price charged by each shop for one bag of rice.
Output Format : 
For each test case, print the minimum cost to complete the task.

Output for each test case will be printed on 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
1 ≤ W ≤ 500
-1 ≤ COST[i] ≤ 10^5 

Time limit: 1 sec
Sample Input 1 :
2
5 4
100 5 -1 100 100
5 1
-1 5 -1 100 100
Sample Output 1 :
10
-1
Explanation For Sample Input 1 :
For test case 1 :
We will print 10 because:
we can buy two bags of rice from the 2’nd shop. This shop sells rice in packing of 2kgs each and sells each bag for COST[1] = 5. Therefore we have to pay a total cost of 2 * 5 = 10 to complete this task.

For test case 2 : 
We will print -1 because:
We need to buy exactly 1kg of rice, and in order to complete this task we only have one option, that is to buy one bag of rice from the 1’st shop. But we can’t complete this task as the 1’st shop is closed.
Sample Input 2 :
2
17 138
40 28 7 21 59 48 74 15 63 24 81 14 31 7 35 -1 13
12 63
35 43 40 18 80 64 63 99 50 51 36 31
Sample Output 2 :
77
178
Hint

Think of a recursive approach that can later be memoized to solve optimally.

Approaches (3)
Recursion

One will get a clear intuition that a simple greedy approach will not work. A naive recursive approach that can later be extended to implement a DP solution is discussed here.

 

Let (i, j) recursive call return the minimum cost to buy exactly ‘j’ kgs of rice only from the first ‘i’ shops, then to calculate (i, j): we can avoid buying anything from the i’th shop, in this case, we will make a transition from (i-1, j) -> (i, j). If in case we plan to buy rice bags from the i’th shop then there can be two conditions, the first one is the case where we are buying from the i’th shop for the first time, in this case, we will make a transition of (i-1, j-i) -> (i, j). Another case here can be, when we have already bought a bag from the i’th shop and plan to buy more bags from the i’th shop now, in this case, in this case, we will make a transition from (i, j-i) -> (i, j). Remember that the answer for (i, j) will be the minimum value amongst the three transitions discussed above.

 

Our final answer will be the minimum of all the recursive calls (i, W) for 1 ≤ i ≤ N.

 

The steps are as follows :

  1. Initialize a variable ‘Price’ to INT_MAX, this variable will store the final answer.
  2. Make initial recursive calls (i, W) for all 1 ≤ i ≤ N, update the value of ‘Price’ so that it stores the minimum value returned by these recursive calls.
  3. In the recursive function:
    • End the recursion using base condition when either ‘i’ or ‘j’ equals 0.
    • Initialize a variable ‘curAns’ to store the answer for the (i, j) recursive call.
    • Do the first transition from (i-1, j) to (i, j).
    • If the Cost[i-1] is not equal to -1, then do the other two transitions: (i-1, j-i) to (i, j) and (i, j-i) to (i, j).
    • Update ‘curAns’ to store the minimum value of all these three transitions, and finally return this value to end the current recursive call.
  4. Finally, check if ‘Price’ is still equal to INT_MAX, this means that it is not possible to buy the rice and we will return -1 in this case. Else return the value stored in ‘Price’.
Time Complexity

O( 3 ^ ( N * W ) ), where N denotes the number of shops and W denotes the amount of rice.

 

To calculate each of the (i, j) values, we require exactly three recursive calls. The value of ‘i’ here can range from [0, N] and the value of ‘j’ can range from [0, W].

Hence the time complexity is O( 3 ^ (N*W)  ).

Space Complexity

O( N * W ), where N denotes the number of shops and W denotes the amount of rice.

 

There can be at max ~(N*W) calls in the recursion stack in the worst case.

Hence the space complexity is O( N*W ).

Code Solution
(100% EXP penalty)
Minimum Cost to Buy Rice
Full screen
Console