[Google Coding Problem] Help

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.

Query Definition

  • The first element represents an integer C = Query[i][0]
  • The Second element represents an integer K = Query[i][1]
  • The next K integers representing indices of broken toys.

Example

  • N = 6

  • A = [3,6,2,1,4,5]

  • Q = 1

  • Query = [[10, 2, 2, 5]]

  • C = 10, K = 2

  • Broken toys are represented by indices [2,5]

  • you purchase the toys 1,3 and 6 which cost us a total of A[i] + A[3] + A[6] = 3 + 2 + 5 = 10. Therefore you buy 3 toys using 10 amount 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.

This Might Work, Hoping I’m Not Wrong.

  1. Removing Broken Toys from Array
  2. Sorting The Remaining Array

Then
• Consequtive Addition Until The Sum is > or = Money You Have

Or

• Using Binary Search to Check If Sum of Sub-array [0, mid] is >, < or = to Money.
If > Then:
Moving To The Left- part
if < Then:
Moving To The Right-part
if = Then:
You Got Your Answer

If Still >, < After BS:
From Last Index Of BS Start Adding/Subtracting (<, >).
until You Find Sum Which is <=.