Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Minimum Cost To Buy Oranges

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

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 )
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.
Full screen
Console