Show problems as
Classic problem #1833MediumArrayGreedySortingCounting Sort

Maximum Ice Cream Bars

Real-world version: Flea Market Record Haul
Tracked in this browser only
Read Maximum Ice Cream Bars on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A collector arrives at a flea market holding budget tokens, the only currency the stalls accept.

One stall has a crate of second-hand records laid out. Record i is tagged at prices[i] tokens. The collector may take away any group of records, in any combination, as long as the tags of the records taken add up to no more than budget. Records are sold whole: there is no haggling, no swapping and no part payment, and each record in the crate can be taken at most once even when two of them carry the same tag.

Return the largest number of records the collector can walk away with.

Examples

Example 1

Input
prices = [9, 4, 12, 4, 30], budget = 17
Output
3

Taking the two records tagged 4 and the one tagged 9 uses 4 + 4 + 9 = 17 tokens, which is the whole budget, and hands over three records.

Example 2

Input
prices = [10, 3, 3, 3], budget = 11
Output
3

The three records tagged 3 cost 9 tokens together, leaving 2 tokens unspent and three records in hand.

Example 3

Input
prices = [40, 25], budget = 12
Output
0

Both tags are above the whole budget, so nothing can be taken and the collector leaves empty-handed.

Constraints

  • prices.length == n
  • 1 <= n <= 10^5
  • 1 <= prices[i] <= 10^5
  • 1 <= budget <= 10^8

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_records(prices: list[int], budget: int) -> int:
Java
public int maxRecords(int[] prices, int budget)

More on the same topics