You are having a party and want to order cakes for your guests from a nearby Eatery. The Eatery has enough different types of cakes to faciliatate your guests. But there are some conditions to it
- You can only order at-most one type of each cake
- Each type of cake has it's own number of slices.
You estimated the maximum number of slices that you want to order for your guests based on the number of registered guests list. In order to reduce food waste, your goal is to order as many slices as possible, but not more than the maximum number.
You are provided with two Strings S1 and S2, where
- S1 = "17 4" , where 17 is the maximum number of cake slices that we want to order, and 4 is the type of cakes that we have.
- S2 = "2 5 6 8" , where 2 5 6 8 is the respective number of slices in each type pf cake, from c0 to cn.
Your solution should return an array of integer stating the number of cakes that we can select to order which are less than or equal to the maximum number of slices that we need. In this case, it should return {2, 6, 8}
Limits
- An integer M (1 ≤ M ≤ 10^9) – the maximum number of cake slices to order
- An integer N (1 ≤ N ≤ 10^5) – the number of different types of Cake
Note: Kindly consider the limits before suggesting knapsack as a solution