Maximize Cards Bought Within a Budget
Problem statement
You are buying birthday cards for a friend. Each card has a printed number that equals its cost. You only want to give cards the recipient does not already own, and you have a fixed budget. You want to give as many cards as possible -- you are maximizing the count of new cards, not their total value.
Given the list all_costs of every card's cost, the list owned of cards the recipient already has, and an integer budget, return the maximum number of not-yet-owned cards you can buy without exceeding the budget. Cards are identified by their printed number: if a number appears in owned, every card with that number in all_costs is excluded, while repeated numbers not in owned are separate cards that can each be bought.
Complete:
def maxCards(all_costs: list[int], owned: list[int], budget: int) -> int:
Constraints:
- $1 \le \text{len(all\_costs)} \le 10^5$, costs are positive integers.
- $0 \le \text{budget} \le 10^9$.
Examples:
all_costs = [2, 5, 1, 8],owned = [5],budget = 4-> available costs are[1, 2, 8]; buy1then2(total3), cannot afford8, so the answer is2.all_costs = [3, 3, 7],owned = [],budget = 6-> buy both3s, the answer is2.all_costs = [10, 20],owned = [10, 20],budget = 100-> nothing is available, the answer is0.
Show hint
When the goal is the number of items rather than their total worth, which items does a budget stretch furthest on?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.