Welcome to Subscribe On Youtube
1357. Apply Discount Every n Orders
Description
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 i^{th}
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 j^{th}
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 j^{th} product)
.
The supermarket decided to have a sale. Every n^{th}
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 withn
, thediscount
, and theproducts
and theirprices
.double getBill(int[] product, int[] amount)
Returns the final total of the bill with the discount applied (if any). Answers within10^{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. 1^{st} customer, no discount. // bill = 1 * 100 + 2 * 200 = 500. cashier.getBill([3,7],[10,10]); // return 4000.0. 2^{nd} 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. 3^{rd} customer, 50% discount. // Original bill = 1600 // Actual bill = 1600 * ((100  50) / 100) = 800. cashier.getBill([4],[10]); // return 4000.0. 4^{th} customer, no discount. cashier.getBill([7,3],[10,10]); // return 4000.0. 5^{th} customer, no discount. cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); // return 7350.0. 6^{th} 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. 7^{th} customer, no discount.
Constraints:
1 <= n <= 10^{4}
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 inproducts
.1 <= amount[j] <= 1000
 The elements of
product
are unique.  At most
1000
calls will be made togetBill
.  Answers within
10^{5}
of the actual value will be accepted.
Solutions
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.
The time complexity of initialization is $O(n)$, where $n$ is the number of products. The time complexity of the getBill
function is $O(m)$, where $m$ is the number of products purchased. The space complexity is $O(n)$.

class Cashier { private int i; private int n; private int discount; private Map<Integer, Integer> d = new HashMap<>(); public Cashier(int n, int discount, int[] products, int[] prices) { this.n = n; this.discount = discount; for (int j = 0; j < products.length; ++j) { d.put(products[j], prices[j]); } } public double getBill(int[] product, int[] amount) { int dis = (++i) % n == 0 ? discount : 0; double ans = 0; for (int j = 0; j < product.length; ++j) { int p = product[j], a = amount[j]; int x = d.get(p) * a; ans += x  (dis * x) / 100.0; } return ans; } } /** * Your Cashier object will be instantiated and called as such: * Cashier obj = new Cashier(n, discount, products, prices); * double param_1 = obj.getBill(product,amount); */

class Cashier { public: Cashier(int n, int discount, vector<int>& products, vector<int>& prices) { this>n = n; this>discount = discount; for (int j = 0; j < products.size(); ++j) { d[products[j]] = prices[j]; } } double getBill(vector<int> product, vector<int> amount) { int dis = (++i) % n == 0 ? discount : 0; double ans = 0; for (int j = 0; j < product.size(); ++j) { int x = d[product[j]] * amount[j]; ans += x  (dis * x) / 100.0; } return ans; } private: int i = 0; int n; int discount; unordered_map<int, int> d; }; /** * Your Cashier object will be instantiated and called as such: * Cashier* obj = new Cashier(n, discount, products, prices); * double param_1 = obj>getBill(product,amount); */

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)

type Cashier struct { i int n int discount int d map[int]int } func Constructor(n int, discount int, products []int, prices []int) Cashier { d := map[int]int{} for i, product := range products { d[product] = prices[i] } return Cashier{0, n, discount, d} } func (this *Cashier) GetBill(product []int, amount []int) (ans float64) { this.i++ dis := 0 if this.i%this.n == 0 { dis = this.discount } for j, p := range product { x := float64(this.d[p] * amount[j]) ans += x  (float64(dis)*x)/100.0 } return } /** * Your Cashier object will be instantiated and called as such: * obj := Constructor(n, discount, products, prices); * param_1 := obj.GetBill(product,amount); */