MARTO - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Ayush Nagal

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Greedy Algo, Sorting

PROBLEM:

A person has k amount of money to buy some items whose prices are given. We have to find the maximum number of items that a person can buy with k amount of money.

EXPLANATION:

First of all, we need to applying sorting to sort the given array, which consists of prices of each item. We can use any sorting algo like merge sort, quick sort, etc. In C++, we have inbuilt function to sort, we use it in the following manner:
sort(arr, arr+n);
After that, we need to pick items starting from the cheapest one.

for(int i=0;i<n;i++)
{
    if(sum+arr[i]<=k)
    {
        sum+=arr[i];
        count++;
    }
}

AUTHOR’S SOLUTION:

Author’s solution can be found here.

3 Likes