# PROBLEM LINK:

**Author:** Puneet Gupta

**Editorial:** Puneet Gupta

# DIFFICULTY:

EASY

# PREREQUISITES:

GREEDY, IMPLEMENTATION

# PROBLEM:

Our task is to take largest amount of toys Riku doesn’t have such that the sum of their costs doesn’t exceed M.

# EXPLANATION:

To do this, one can perform greedy algorithm: let’s buy the cheapest toy that Riku doesn’t have at every step, while the amount of money left is sufficient to do that.

A boolean array can be used as a handle, storing true values, in indices equal to the type of toys which Riku already has.

So we just need to iterate over our handle and check if corresponding value for a given index is equal to false, we should buy it, otherwise we can’t.

The solution complexity is O(n + \sqrt{m}).

One can use the <> data structure (C++ \texttt{std::set}, for example), for storing the types Riku has at the moment. In this case the complexity is O(n + \sqrt{m} log(n)).

# AUTHOR’S SOLUTION:

Author’s solution can be found here.