1357. Apply Discount Every n Orders

Problem¶

Implement a cashier that prices each order and applies a percentage discount to every \(n\)th customer.

Example: With prices {1: 10, 2: 20}, a 50% discount every third customer, and three identical orders of one item 1 and one item 2, the bills are 30, 30, and 15.

class Cashier:
    def __init__(self, n: int, discount: int, products: list[int],
    prices: list[int]):
        pass

    def getBill(self, product: list[int], amount: list[int]) -> float:
        pass

Key trick¶

Keep a customer counter and a product-ID-to-price dictionary. Apply the discount when the counter is divisible by \(n\).

Trap¶

Count orders, not products. Also, product IDs are not necessarily array indices.

Why is it interesting?¶

It combines a simple pricing calculation with persistent state across calls.

Python solution¶

class Cashier:
    def __init__(self, n: int, discount: int, products: list[int], prices: list[int]):
        self.n = n
        self.discount = discount
        self.prices = dict(zip(products, prices))
        self.customer_count = 0

    def getBill(self, product: list[int], amount: list[int]) -> float:
        self.customer_count += 1
        total = sum(
            self.prices[p_id] * quantity
            for p_id, quantity in zip(product, amount)
        )

        if self.customer_count % self.n == 0:
            return total * (100 - self.discount) / 100
        return float(total)

Construction takes \(O(p)\) time and space for \(p\) products. Each bill takes \(O(k)\) time for \(k\) purchased products and \(O(1)\) extra space.

Comment on my solution¶

Your solution is correct and has the intended \(O(k)\) time per bill. You can simplify it by mapping product IDs directly to prices; then you do not need copied product and price arrays or an index lookup.

class Cashier:

    def __init__(self, n: int, discount: int, products: list[int], prices: list[int]):
        self.n = n
        self.discount = discount
        self.products = products[:]
        self.prices =prices[:]
        self.customer_count = 0
        self.index = {p_id:i for i, p_id in enumerate(products)}


    def getBill(self, product: list[int], amount: list[int]) -> float:
        self.customer_count += 1
        total = 0
        for p_id, amount in zip(product, amount):
            idx = self.index[p_id]
            price = self.prices[idx] * amount
            total += price
        if self.customer_count % self.n == 0:
            return total * ((100 - self.discount) / 100)
        return total