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)