Frontend School

Clearance Sale: Maximize Items with 'Buy K-1 Get 1 Free' Offer

DSA
medium

Clearance Sale: Maximize Items with 'Buy K-1 Get 1 Free' Offer

Medium
Greedy
Sorting
Arrays

Overview

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.

What you need to do / Task

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.

  • The offer states: for every K-1 items a customer purchases, they get the K-th item for free.
  • The customer wants to maximize the total number of items they acquire.
  • They cannot exceed their given budget.

Input & output

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:

  • An integer representing the maximum total number of items the customer can acquire.

Clarifications

  • Empty costs array: If costs is empty, no items can be acquired, so the result should be 0.
  • Insufficient budget: If the budget is too low to even acquire the cheapest item, 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.
  • Order of items: Items can be chosen in any order. The offer applies to the K-th item acquired in sequence. To maximize items, a greedy strategy considering the cheapest available items is generally optimal.

Examples

1

Example 1

Input:

costs = [10, 20, 30, 40, 50, 60], budget = 100, k = 3

Output:

4

Note:

  1. Sort costs: [10, 20, 30, 40, 50, 60].
  2. Buy 10 (paid), total_spent = 10, items_acquired = 1.
  3. Buy 20 (paid), total_spent = 30, items_acquired = 2.
  4. Acquire 30 (free, as it's the 3rd item), total_spent remains 30, items_acquired = 3.
  5. Buy 40 (paid), total_spent = 70, items_acquired = 4.
  6. Attempt to buy 50 (paid), total_spent would be 120, which exceeds budget = 100. Stop. Maximum items acquired: 4.
2

Example 2

Input:

costs = [5, 5, 5, 5, 5], budget = 12, k = 2

Output:

4

Note:

  1. Sort costs: [5, 5, 5, 5, 5].
  2. Buy 5 (paid), total_spent = 5, items_acquired = 1.
  3. Acquire 5 (free, as it's the 2nd item), total_spent remains 5, items_acquired = 2.
  4. Buy 5 (paid), total_spent = 10, items_acquired = 3.
  5. Acquire 5 (free, as it's the 4th item), total_spent remains 10, items_acquired = 4.
  6. Attempt to buy 5 (paid), total_spent would be 15, which exceeds budget = 12. Stop. Maximum items acquired: 4.
3

Example 3

Input:

costs = [20, 30, 10], budget = 5, k = 2

Output:

0

Note:

  1. Sort costs: [10, 20, 30].
  2. Attempt to buy 10 (paid), total_spent would be 10, which exceeds budget = 5. Stop. Maximum items acquired: 0.

Constraints

Constraints & assumptions

  • 1 <= costs.length <= 10^5
  • 1 <= costs[i] <= 10^4
  • 0 <= budget <= 10^9
  • 1 <= k <= 10^5
  • All input values are integers.

What interviewers evaluate

  • Correct Greedy Strategy: The candidate correctly identifies and implements the greedy strategy of sorting costs in ascending order and applying the 'K-1 pay, 1 free' rule sequentially.
  • Budget Management: The solution accurately tracks the total budget spent and stops acquiring items once the budget is exceeded.
  • Edge Case Handling: The solution correctly handles edge cases like empty inputs, insufficient budget, or specific values of k (e.g., k=1, or k larger than costs.length).
  • Time Complexity: The solution achieves an optimal time complexity of O(N log N) due to sorting, and O(N) for iteration.
  • Code Quality: The code is well-organized, readable, and uses meaningful variable names.

Loading editor...