| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
Medium |
1429 |
Biweekly Contest 20 Q2 |
|
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 withn, thediscount, and theproductsand theirprices.double getBill(int[] product, int[] amount)Returns the final total of the bill with the discount applied (if any). Answers within10-5of 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] <= 1000- The elements in
productsare unique. 1 <= product.length <= products.lengthamount.length == product.lengthproduct[j]exists inproducts.1 <= amount[j] <= 1000- The elements of
productare unique. - At most
1000calls will be made togetBill. - Answers within
10-5of the actual value will be accepted.
Use a hash table
The time complexity of initialization is getBill function is
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)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);
*/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);
*/