Minimum Cost To Buy Oranges

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
14 upvotes
Asked in companies
IntuitCiscoAmazon

Problem statement

You are given a bag of size 'W' kg and provided with the costs of packets with different weights of oranges as a list/array with the name 'cost'. Every i-th position in the cost denotes the price of 'i+1' kg packet of oranges.

If at any point in time the i-th cost is -1, it means that 'i+1' kg packet of orange is unavailable.

You are required to find the minimum total cost to buy exactly 'W' kg oranges and if it's not possible to buy precisely W kg oranges then print -1. There is an infinite supply of all available packet types.

Note : 
Array index 'i' denotes the cost of (i+1)kg packet. 
Example: cost[0] is the cost of a 1kg packet of oranges.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of each test case contains two single space-separated integers 'N' and 'W' where 'N' denotes the size of the array/list(cost), and 'W' is the bag's size.

The second line of each test case contains 'N' single space-separated integers denoting the values of the cost.
Output Format : 
Print the minimum cost to buy exactly W kg oranges. If it's impossible, print "-1".
Note : 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints : 
1 <= N <= 1000
1 <= W <= 1000
-1 <= cost[i] <= 1000000

Time Limit: 1sec
Sample Input 1 :
5 5
20 10 4 50 100
Sample Output 1 :
14
 Explanation Of Sample Input 1 :
The optimal solution is to buy one bag of 2kg packet and one bag of 3kg packet.
Total Cost = 10 + 4 = 14
Sample Input 2 :
5 5
-1 -1 4 5 -1
Sample Output 2 :
-1
 Explanation Of Sample Input 2 :
It's impossible to buy exactly 5kg oranges, so the answer is -1.
Hint

Try to explore all the possibilities, i.e. taking or skipping all ‘i’ kg packets for all the possible values of weights from 0 to W.

Approaches (4)
Recursive Approach

Write a recursive function minCostToBuyOrangesHelper(idx, requiredWeight, n) to return the Minimum cost to buy exactly requiredWeight Kg oranges with (idx+1) Kg to N kg packets.

  1. Our minimum cost for weight W will be : minCostToBuyOrangesHelper(idx, W, n)
  2. Now at any instant (idx, requiredWeight, n), we have two options:
    1. The option of taking this packet:
cost[idx] + minCostToBuyOrangesHelper(idx, requiredWeight - (idx + 1), n, cost)

        2. The option of skipping this packet and moving to the next packet:

minCostToBuyOrangesHelper(idx + 1, requiredWeight, n, cost)

3. We will take the minimum of these two options as the minimum cost for instant minCostToBuyOrangesHelper(idx, requiredWeight, n)

4. Base cases are:

  1. When requiredWeight is 0 then return 0.
  2. if we reached the end and idx = n and requiredWeight != 0 then return maximum value (INT_MAX) as now it’s impossible to buy the requiredWeight.
  3. If requiredWeight != 0 and requiredWeight  < (idx+1) then return maximum value (INT_MAX) as it’s impossible to buy requiredWeight  from greater weight packets.
    4. Also, take care of packets which are not available. The minimum cost for those idx  will have only one option:
    1. The option of skipping this packet and moving to the next packet:
minCostToBuyOrangesHelper(idx + 1, requiredWeight, n, cost)
Time Complexity

O((2^W)*N), where ‘N’ is the number of packets of different weight, and ‘W’ is the required weight.

 

There are 2 possibilities for each requiredWeight value which gives us the complexity O(2^W) and this requiredWeight can occur with ‘N’ different packets so, Overall Time Complexity is O((2^W)*N).

Space Complexity

O(W), where ‘W’ is the required weight.

 

The recursive call stack can have a maximum depth of ‘W’ as the recursion call will return after requiredWeight become 0 or ( idx+1 >  requiredWeight ).

Code Solution
(100% EXP penalty)
Minimum Cost To Buy Oranges
Full screen
Console