This was asked in coding round of Google.
You are given
N toys in a shop. The cost of each toy is represented by an array A. You have a C amount of money which you can use to purchase the toys. Also there are K broken toys and you won’t purchase them.
For each Q queries, determine maximum number of toys you can purchase using C amount of money.
- The first element represents an integer
C = Query[i]
- The Second element represents an integer
K = Query[i]
- The next
Kintegers representing indices of broken toys.
N = 6
Q = 1
[[10, 2, 2, 5]]
C = 10, K = 2
Broken toys are represented by indices
you purchase the toys 1,3 and 6 which cost us a total of
A[i] + A + A = 3 + 2 + 5 = 10. Therefore you buy
10amount of money.
I don’t have the constraints for the problem, i though of applying knapsack dp for each query but this might be TLE. If anyone can suggest any approach or similar problem to practice such problem.