mediumGreedyPattern: Greedy
Maximum Elements Within Sum Constraint Solution
Problem Statement
Given an array of positive integers `itemCosts`, where `itemCosts[i]` represents the cost of the i-th item, and an integer `maxBudget`, determine the maximum number of items that can be purchased such that their cumulative cost does not exceed `maxBudget`.
Examples
Example 1:
Input:itemCosts = [10, 20, 30, 40], maxBudget = 50
Output:2
Explanation: To maximize the number of items within the budget, we should prioritize purchasing the least expensive items first.
1. Sort `itemCosts`: `[10, 20, 30, 40]`.
2. Purchase item with cost 10. Remaining budget: `50 - 10 = 40`. Items purchased: 1.
3. Purchase item with cost 20. Remaining budget: `40 - 20 = 20`. Items purchased: 2.
4. The next item costs 30, which is more than the remaining budget of 20. So, we cannot purchase any more items.
Thus, the maximum number of items that can be purchased is 2.
Example 2:
Input:itemCosts = [1, 1, 1, 100], maxBudget = 2
Output:2
Explanation: 1. Sort `itemCosts`: `[1, 1, 1, 100]`.
2. Purchase first item with cost 1. Remaining budget: `2 - 1 = 1`. Items purchased: 1.
3. Purchase second item with cost 1. Remaining budget: `1 - 1 = 0`. Items purchased: 2.
4. The next item costs 1, which is more than the remaining budget of 0. Stop.
Maximum items: 2.
Constraints
- `1 <= itemCosts.length <= 10^5`
- `1 <= itemCosts[i] <= 10^4`
- `0 <= maxBudget <= 10^9`
- All `itemCosts[i]` are integers.
Time: O(N log N) Space: O(1)
The optimal approach is a greedy one: to maximize the number of items, we should always prioritize buying the cheapest items first. This involves sorting the `itemCosts` array in ascending order and then iterating through the sorted items, accumulating their costs until the `maxBudget` is exceeded. The time complexity is dominated by sorting, resulting in O(N log N).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
def solve():
# Read itemCosts from the first line of stdin
item_costs_str = sys.stdin.readline().strip()
item_costs = list(map(int, item_costs_str.split()))
# Read maxBudget from the second line of stdin
max_budget = int(sys.stdin.readline().strip())
# Sort the item costs in ascending order
item_costs.sort()
purchased_count = 0
current_cost = 0
for cost in item_costs:
if current_cost + cost <= max_budget:
current_cost += cost
purchased_count += 1
else:
# Cannot afford this item or any subsequent more expensive items
break
print(purchased_count)
if __name__ == '__main__':
solve()