Mark has a million dollars for toys? I wanna be Mark.

Mark will able to maximize the amount of toys he can buy by getting as many of the cheapest ones as his budget allows. This is a good tip torwards sorting the array - as well as this problem falling under the Sorting category, of course.

However, there is one interesting thing to notice. If you think about bubble sort, it always drags the highest value it can find to the far end of the array, repeating that process but stopping one position before each time, until the end poition matches the beggining the array, meaning that it is sorted. With that in mind, if we sort the array in a decreasing order, dragging the smallest value to the end, we can say for sure that the value at the end position after each iteration is the smallest one we found this round.

What does this mean? That you don't have to sort the entire array. After each bubble sort pass, make Mark buy the cheapest toy you found in it and deduct it from his budget. If you reach a point where he can't afford the cheapest toy in a pass, then he won't be able to afford any of the remaining and already have the maximum number of toys he could have bought, so you can abort your sorting there to save some time.

Are you kidding me? How is this a 35 point question.. ?!? Some of the 20 point questions above were a lot harder.

static int maximumToys(int[] prices, int k) {

     int count=0,sum=0;  
     Arrays.sort(prices);  
     for(int i=0;i<prices.length;i++)
     {
         if(sum <= k)
         {
             sum=sum+prices[i];
             count++;
         }


     }
     return count-1;


  Very simple Java solution

tests don't include the case of 1 toy. I had an implementation that passed all the tests but failed the following input:

1 50
45