Clearance Sale: Maximize Items with 'Buy K-1 Get 1 Free' Offer
At Amazon, we're always looking for innovative ways to delight customers, especially during high-demand events like clearance sales. Imagine you're part of the team designing a special promotional offer. We want to maximize customer acquisition during a limited-time "Buy K-1, Get 1 Free" event. Your task is to help customers strategically acquire the maximum number of items given a fixed budget and a list of item costs.
Implement a function maxItemsWithOffer that determines the maximum number of items a customer can acquire during a clearance sale, given their budget and the special offer.
K-1 items a customer purchases, they get the K-th item for free.Function Signature:
function maxItemsWithOffer(costs: number[], budget: number, k: number): number
Input:
costs: An array of integers representing the individual costs of available items.budget: An integer representing the total budget the customer has.k: An integer representing the 'K' in the "Buy K-1, Get 1 Free" offer. For every K items acquired, K-1 are paid for, and one is free.Output:
costs array: If costs is empty, no items can be acquired, so the result should be 0.k = 1: If k is 1, it means "Buy 0, Get 1 Free". Every item is free. The customer can acquire all items, and the total cost will be 0. Your solution should handle this correctly.K-th item acquired in sequence. To maximize items, a greedy strategy considering the cheapest available items is generally optimal.Examples
Example 1
Input:
costs = [10, 20, 30, 40, 50, 60], budget = 100, k = 3
Output:
4
Note:
[10, 20, 30, 40, 50, 60].total_spent = 10, items_acquired = 1.total_spent = 30, items_acquired = 2.total_spent remains 30, items_acquired = 3.total_spent = 70, items_acquired = 4.total_spent would be 120, which exceeds budget = 100. Stop.
Maximum items acquired: 4.Example 2
Input:
costs = [5, 5, 5, 5, 5], budget = 12, k = 2
Output:
4
Note:
[5, 5, 5, 5, 5].total_spent = 5, items_acquired = 1.total_spent remains 5, items_acquired = 2.total_spent = 10, items_acquired = 3.total_spent remains 10, items_acquired = 4.total_spent would be 15, which exceeds budget = 12. Stop.
Maximum items acquired: 4.Example 3
Input:
costs = [20, 30, 10], budget = 5, k = 2
Output:
0
Note:
[10, 20, 30].total_spent would be 10, which exceeds budget = 5. Stop.
Maximum items acquired: 0.Constraints
1 <= costs.length <= 10^51 <= costs[i] <= 10^40 <= budget <= 10^91 <= k <= 10^5k (e.g., k=1, or k larger than costs.length).Loading editor...