We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Apply Discount Every n Orders

Difficulty: Medium

Problem 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 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).

Key Insights

  • We need to track the number of customers to determine when to apply discounts.
  • A mapping from product IDs to their prices can be efficiently managed using a hash table.
  • The discount is applied only on every nth customer; otherwise, the total bill is calculated without discount.

Space and Time Complexity

Time Complexity: O(m), where m is the number of items in the current customer's bill. Space Complexity: O(k), where k is the number of unique products in the supermarket.

Solution

The solution involves creating a Cashier class that initializes with the number of customers that will receive discounts, the discount percentage, and the products and their prices. The getBill method computes the total bill for the current customer's purchase by iterating through the products they bought, calculating the subtotal based on the prices from the mapping. After calculating the subtotal, the method checks if the current customer is eligible for a discount and applies it if they are. We maintain a count of the total customers served to track when to apply the discount.

Code Solutions

class Cashier:
    def __init__(self, n: int, discount: int, products: List[int], prices: List[int]):
        self.n = n  # Number of customers for discount
        self.discount = discount / 100  # Convert percentage to decimal
        self.product_price_map = dict(zip(products, prices))  # Map product ID to price
        self.total_customers = 0  # Count of total customers

    def getBill(self, product: List[int], amount: List[int]) -> float:
        self.total_customers += 1  # Increment customer count
        subtotal = sum(self.product_price_map[product[i]] * amount[i] for i in range(len(product)))  # Calculate subtotal
        if self.total_customers % self.n == 0:  # Check if this is an n-th customer
            return subtotal * (1 - self.discount)  # Apply discount
        return subtotal  # No discount
← Back to All Questions