# Maximize Toys

Given an array a[ ] of length N consisting cost of N toys and an integer K depicting the amount with you. Your task is to find maximum number of toys you can buy with K amount.

Example 1:

```
Input:
n = 7
k = 50
a[] = {1, 12, 5, 111, 200, 1000, 10}
Output: 4
Explaination: The costs of the toys
you can buy are 1, 12, 5 and 10.
```

Example 2:

```
Input:
n = 3
k = 100
a[] = {20, 30, 50}
Output: 3
Explaination: You can buy all toys.
```

**Algorithm: Greedy approach**

- sort the array
- traverse through the array
- take a sum variable and keep addings elements to it and everytime we add an element to sum increment the counter ,once the sum is greater than k return counter.

**c++ implementation:**

** int toyCount(int n, int k, int a[])
{
sort(a,a+n);
int sum=0;int count=0;
for(int i=0;i<n;i++)
{
if(sum<k)
{
sum=sum+a[i];
count++;
if(sum>k)
{
count--;
}
}
else
return count;
}
}**

Time Complexity : O(nlogn)

Space Complexity: O(1)

Space Complexity: O(1)