There is a supermarket that is frequented by many customers. The products sold at the supermarket are represented as two parallel integer arrays products and prices, where the ith product has an ID of products[i] and a price of prices[i].
When a customer is paying, their bill is represented as two parallel integer arrays product and amount, where the jth product they purchased has an ID of product[j], and amount[j] is how much of the product they bought. Their subtotal is calculated as the sum of each amount[j] * (price of the jth product).
The supermarket decided to have a sale. Every nth customer paying for their groceries will be given a percentage discount. The discount amount is given by discount, where they will be given discount percent off their subtotal. More formally, if their subtotal is bill, then they would actually pay bill * ((100 - discount) / 100).
Implement the Cashier class:
Cashier(int n, int discount, int[] products, int[] prices) Initializes the object with n, the discount, and the products and their prices.double getBill(int[] product, int[] amount) Returns the final total of the bill with the discount applied (if any). Answers within 10-5 of the actual value will be accepted.Example 1:
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 <= 1040 <= discount <= 1001 <= products.length <= 200prices.length == products.length1 <= products[i] <= 2001 <= prices[i] <= 1000products are unique.1 <= product.length <= products.lengthamount.length == product.lengthproduct[j] exists in products.1 <= amount[j] <= 1000product are unique.1000 calls will be made to getBill.10-5 of the actual value will be accepted.The key idea in #1357 Apply Discount Every n Orders is to design a system that tracks customer orders and applies a discount after every n orders. This problem is primarily about implementing an efficient design using arrays and hash tables.
First, store product prices in a hash map for constant-time lookups. Each time a customer order arrives, calculate the total bill by multiplying each product's price with its ordered quantity. Maintain an internal orderCount to track how many orders have been processed.
Whenever orderCount % n == 0, apply the given percentage discount to the computed bill. Otherwise, return the normal total. This design ensures fast price retrieval and efficient order processing.
Because each order processes only the listed products, the runtime depends on the number of items in the order, while the price lookup remains constant time using the hash table.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Order Counter Design | O(k) per order, where k is the number of products in the order | O(p) where p is the number of products stored in the price map |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Keep track of the count of the customers.
Check if the count of the customers is divisible by n then apply the discount formula.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, similar design-style problems appear frequently in FAANG and other top tech company interviews. They test your ability to implement classes, manage state across function calls, and use hash maps effectively.
Tracking the order count helps determine when the discount should be applied. By checking whether the current order number is a multiple of n, the system can easily apply the discount at the correct intervals.
A hash table is the most suitable data structure because it allows constant-time price lookups for products. This keeps the order processing efficient even when many products exist in the system.
The optimal approach uses a hash map to store product prices and a counter to track the number of processed orders. Each order calculates the total price using quick lookups, and a discount is applied whenever the order count is divisible by n.