LeetCode Problem Workspace
Apply Discount Every n Orders
Compute customer bills with periodic discounts efficiently using array scanning and hash mapping for fast product price lookups.
3
Topics
4
Code langs
3
Related
Practice Focus
Medium · Array scanning plus hash lookup
Answer-first summary
Compute customer bills with periodic discounts efficiently using array scanning and hash mapping for fast product price lookups.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for Array scanning plus hash lookup
This problem requires tracking each customer's order count to apply discounts correctly while efficiently computing totals. Use hash maps to quickly find product prices, multiplying by quantities to get subtotals. Every nth order receives a percentage discount applied directly to the computed subtotal before returning the final bill.
Problem Statement
A supermarket sells products represented by two parallel arrays: products and prices. Each products[i] has a price prices[i]. Customers purchase items recorded in arrays product and amount, where product[j] is the item ID and amount[j] is the quantity purchased. Calculate each customer's subtotal as the sum of prices times quantities.
The supermarket offers a promotion where every nth customer receives a discount. The discount percent is given by discount. For eligible customers, reduce the subtotal by discount percent, i.e., final bill = subtotal * (100 - discount)/100. Implement a system to return the correct bill for multiple customers called sequentially.
Examples
Example 1
Input: See original problem statement.
Output: See original problem statement.
Input ["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"] [[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]] Output [null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0] Explanation Cashier cashier = new Cashier(3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]); cashier.getBill([1,2],[1,2]); // return 500.0. 1st customer, no discount. // bill = 1 * 100 + 2 * 200 = 500. cashier.getBill([3,7],[10,10]); // return 4000.0. 2nd customer, no discount. // bill = 10 * 300 + 10 * 100 = 4000. cashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]); // return 800.0. 3rd customer, 50% discount. // Original bill = 1600 // Actual bill = 1600 * ((100 - 50) / 100) = 800. cashier.getBill([4],[10]); // return 4000.0. 4th customer, no discount. cashier.getBill([7,3],[10,10]); // return 4000.0. 5th customer, no discount. cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); // return 7350.0. 6th customer, 50% discount. // Original bill = 14700, but with // Actual bill = 14700 * ((100 - 50) / 100) = 7350. cashier.getBill([2,3,5],[5,3,2]); // return 2500.0. 7th customer, no discount.
Constraints
- 1 <= n <= 104
- 0 <= discount <= 100
- 1 <= products.length <= 200
- prices.length == products.length
- 1 <= products[i] <= 200
- 1 <= prices[i] <= 1000
- The elements in products are unique.
- 1 <= product.length <= products.length
- amount.length == product.length
- product[j] exists in products.
- 1 <= amount[j] <= 1000
- The elements of product are unique.
- At most 1000 calls will be made to getBill.
- Answers within 10-5 of the actual value will be accepted.
Solution Approach
Use Hash Map for Price Lookup
Create a hash map mapping each product ID to its price. This allows constant-time price lookup when computing subtotals for orders, avoiding repeated array scans for each getBill call.
Track Customer Count
Maintain a counter of how many customers have called getBill. Apply the discount only when the count is a multiple of n. This ensures the correct customer receives the discount consistently without recomputation.
Compute Subtotal with Discount
Iterate over the purchased product IDs, multiply each quantity by its price from the hash map, sum to get subtotal. If eligible, multiply subtotal by (100 - discount)/100 to apply the discount, then return the final bill.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(k) per getBill call, where k is the number of products in the order, due to array iteration and hash lookups. Space complexity is O(m) for the hash map storing m product prices.
What Interviewers Usually Probe
- Check if your hash map avoids repeated array scans for price lookups.
- Make sure discount is applied only on every nth customer and tracked properly.
- Consider edge cases when amount arrays are empty or contain maximum quantities.
Common Pitfalls or Variants
Common pitfalls
- Forgetting to increment the customer counter, causing discounts to be misapplied.
- Incorrectly mapping product IDs to prices leading to wrong subtotal calculation.
- Using nested loops over products for each getBill call, causing unnecessary time complexity.
Follow-up variants
- Vary discount frequency, e.g., every mth customer, to test counter logic.
- Use floating-point prices or discounts to examine precision handling in subtotal computation.
- Allow multiple discounts for different customer groups, requiring separate counters and logic.
FAQ
What pattern does 'Apply Discount Every n Orders' follow?
It follows an array scanning plus hash lookup pattern, using hash maps for price retrieval and counting orders to apply periodic discounts.
How do I handle the discount application correctly?
Maintain a customer count and apply the discount only when the count is a multiple of n, multiplying the subtotal by (100 - discount)/100.
Is it efficient to scan products array for each getBill call?
No, using a hash map for product prices ensures O(1) lookup per item, making each getBill call efficient.
Can amount or product arrays contain duplicate items?
No, each product array per order has unique items, so duplicate handling is unnecessary.
What precision is expected for the final bill?
Answers within 10^-5 of the actual value are accepted, so maintain sufficient floating-point precision during calculations.
Solution
Solution 1: Hash Table + Simulation
Use a hash table $d$ to store the product ID and price, then traverse the product ID and quantity, calculate the total price, and then calculate the price after discount based on the discount.
class Cashier:
def __init__(self, n: int, discount: int, products: List[int], prices: List[int]):
self.i = 0
self.n = n
self.discount = discount
self.d = {product: price for product, price in zip(products, prices)}
def getBill(self, product: List[int], amount: List[int]) -> float:
self.i += 1
discount = self.discount if self.i % self.n == 0 else 0
ans = 0
for p, a in zip(product, amount):
x = self.d[p] * a
ans += x - (discount * x) / 100
return ans
# Your Cashier object will be instantiated and called as such:
# obj = Cashier(n, discount, products, prices)
# param_1 = obj.getBill(product,amount)Continue Practicing
Continue Topic
array
Practice more edge cases under the same topic.
arrow_forwardauto_awesomeContinue Pattern
Array scanning plus hash lookup
Expand the same solving frame across more problems.
arrow_forwardsignal_cellular_altSame Difficulty Track
Medium
Stay on this level to stabilize interview delivery.
arrow_forward