Frontend School

Budget Shopping Spree

DSA
easy

Budget Shopping Spree

Easy
Greedy
Sorting
Arrays

Overview

Imagine you're managing procurement for a new project, and you have a strict budget for acquiring necessary components. There's a list of available components, each with a specific cost. Your goal is to acquire as many distinct components as possible without exceeding your allocated budget. This problem tests your ability to optimize resource allocation under constraints, a common scenario in real-world engineering.

What you need to do / Task

Your task is to implement a function that determines the maximum number of distinct components you can purchase given a list of their individual costs and your total budget.

Input & output

  • Input:
    • costs: An array of numbers, where costs[i] represents the cost of the i-th component.
    • budget: A number representing the total amount of money you have to spend.
  • Output:
    • A single number, representing the maximum count of components you can buy.

Clarifications

  • If the costs array is empty, no items can be bought, so the result should be 0.
  • If the budget is 0, and all items have a cost greater than 0, then 0 items can be bought.
  • All costs are positive integers.
  • You cannot buy fractional items, and each item in the costs array is distinct (you can't buy the same 'type' of item multiple times if it only appears once in the array). You are simply selecting items from the given list.

Examples

1

Example 1

Input:

costs = [10, 20, 30], budget = 50

Output:

2

Note:

To maximize items, we buy the cheapest ones first. Buy the item costing 10 (budget remaining: 40, items: 1). Then buy the item costing 20 (budget remaining: 20, items: 2). The next cheapest item costs 30, which exceeds the remaining budget. So, the maximum items bought is 2.

2

Example 2

Input:

costs = [1, 100, 200], budget = 2

Output:

1

Note:

Buy the item costing 1 (budget remaining: 1, items: 1). The next cheapest item costs 100, which exceeds the remaining budget. Maximum items bought is 1.

3

Example 3

Input:

costs = [7, 3, 6, 2, 5], budget = 15

Output:

3

Note:

Sort the costs: [2, 3, 5, 6, 7].

  1. Buy 2 (budget: 13, items: 1)
  2. Buy 3 (budget: 10, items: 2)
  3. Buy 5 (budget: 5, items: 3)
  4. The next item costs 6, which is more than the remaining budget of 5. Stop. Maximum items bought is 3.

Constraints

Constraints & assumptions

  • 1 <= costs.length <= 10^5
  • 1 <= costs[i] <= 10^9
  • 0 <= budget <= 10^9
  • All costs[i] and budget are integers.

Out of scope

  • Handling non-integer costs or budget values.
  • Considering item weights or other attributes beyond cost.
  • Optimizing for total remaining budget, only for maximum item count.

What interviewers evaluate

  • Correctness: Does the solution accurately determine the maximum number of items?
  • Efficiency: Is the chosen algorithm optimal in terms of time complexity for the given constraints?
  • Greedy Approach: Does the candidate correctly identify and apply the greedy strategy?
  • Code Quality: Is the code clean, readable, and well-structured?

Loading editor...