Mark and Toys

See the original problem on HackerRank.

Solutions

Since we need to maximize the number of toys, we can sort the array in incresing order of price and pick them as long as the budget is available.

A solution in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iterator>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n, k; cin >> n >> k;
    vector<int> prices(n);
    copy_n(istream_iterator<int>(cin), n, begin(prices));
    sort(begin(prices), end(prices));
    auto toys = 0, cost=0;
    for (auto i=0u; i<prices.size() && cost<=k; ++i)
    {
        if (prices[i]+cost<=k)
        {
            cost+=prices[i];
            ++toys;
        }
    }
    cout << toys << endl;
}

In Haskell:

1
2
3
4
5
6
7
8
9
import Data.List (sort)

keepWhileSumBelow k = foldl (\l x -> if sum (x:l) < k then x:l else l) []
maximumToys prices k = length $ keepWhileSumBelow k $ sort prices

main = do
    contents <- getContents
    let (_:k:prices) = map read $ words contents
    print $ maximumToys prices k

Using heap operations

An alternative solution consists in maintaining a min heap:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> prices;

    for (int i = 0; i < n; i++) 
    {
        int price_item; cin >> price_item;

        auto sum = accumulate(begin(prices), end(prices), 0);

        if (sum + price_item <= k) 
        {
            prices.push_back(price_item);
            push_heap(begin(prices), end(prices));
        } 
        else if (sum) 
        {
            pop_heap(begin(prices), end(prices));
            auto last = prices.rbegin();
            *last = min(*last, price_item);
            push_heap(begin(prices), end(prices));
        }
    }

    cout << prices.size() << "\n";
}
sort 
We've worked on this challenge in these gyms: modena  padua  milan  turin 
comments powered by Disqus