Problem Description

The Leetcode problem "Apply Discount Every n Orders" asks you to design a system for a restaurant that applies a discount to every nth order. You are given three parameters:

• n: Every nth customer gets a discount.
• discount: The percentage discount to apply (e.g. 20 for 20%).
• products and prices: Lists of product IDs and their corresponding prices.

You must implement a class so that when getBill(product, amount) is called, it returns the total bill for the customer, applying the discount if this is the nth customer. Each call to getBill represents a new order. Key constraints include:

• Each order is independent, but the system must track how many orders have been processed to apply the discount correctly.
• Do not reuse or share order information between calls.
• Only one valid answer per order; do not double-discount any order.

Thought Process

At first glance, the problem might look like a simple calculation of totals and discounts. However, the challenge is in tracking the number of orders to ensure the discount is applied only on every nth order. We need to:

• Efficiently map product IDs to their prices for quick lookups.
• Maintain a counter to track the number of orders processed so far.
• Apply the discount only when the counter hits a multiple of n.

A brute-force approach would be to keep a list of all orders, but this is unnecessary and inefficient. Instead, we can optimize by using a simple counter and a dictionary for price lookups.

Solution Approach

The solution can be broken down into the following steps:

1. Initialization:
   • Store n and discount as class variables.
   • Create a dictionary mapping product IDs to their prices for O(1) access.
   • Initialize an order counter to zero.
2. Processing an Order:
   • Each time getBill is called, increment the order counter.
   • Calculate the total bill by summing the price times the amount for each product in the order.
   • If the order counter is divisible by n, apply the discount to the total.
   • Return the final bill amount.
3. Why This Works:
   • The dictionary ensures fast price lookup for each product.
   • The counter ensures the discount logic is simple and correct.

Example Walkthrough

Suppose n = 3, discount = 20, products = [1,2,3], prices = [100,200,300].

1. Order 1: getBill([1,2], [1,2])
   • Total = 1×100 + 2×200 = 100 + 400 = 500
   • Order count is 1 (not a multiple of 3), no discount. Return 500.
2. Order 2: getBill([3], [2])
   • Total = 2×300 = 600
   • Order count is 2, no discount. Return 600.
3. Order 3: getBill([1,3], [3,1])
   • Total = 3×100 + 1×300 = 300 + 300 = 600
   • Order count is 3 (multiple of 3), apply 20% discount: 600 × 0.8 = 480. Return 480.
4. Order 4: getBill([2], [1])
   • Total = 1×200 = 200
   • Order count is 4, no discount. Return 200.

This pattern repeats, with every 3rd order receiving the discount.

Time and Space Complexity

• Brute-force Approach:
  • If we stored all orders, space would be O(k) for k orders, and time per order would be O(m) for m products per order.
• Optimized Approach:
  • Time Complexity: O(m) per getBill call, where m is the number of products in the order (since we sum over each product).
  • Space Complexity: O(p) for storing the price mapping, where p is the number of products.
  • No extra space per order, just the counter.

Summary

The key to solving "Apply Discount Every n Orders" efficiently is to use a counter to track orders and a dictionary for quick price lookups. This avoids unnecessary storage and ensures that the discount logic is simple and reliable. The approach is both efficient and easy to maintain, making it an elegant solution to the problem.

Code Implementation

class Cashier:

    def __init__(self, n: int, discount: int, products: List[int], prices: List[int]):
        self.n = n
        self.discount = discount
        self.count = 0
        self.price_map = {pid: price for pid, price in zip(products, prices)}

    def getBill(self, product: List[int], amount: List[int]) -> float:
        self.count += 1
        total = 0
        for pid, amt in zip(product, amount):
            total += self.price_map[pid] * amt
        if self.count % self.n == 0:
            total = total * (100 - self.discount) / 100
        return total
      

class Cashier {
public:
    int n, discount, count;
    unordered_map<int, int> price_map;

    Cashier(int n, int discount, vector<int>& products, vector<int>& prices) {
        this->n = n;
        this->discount = discount;
        count = 0;
        for (int i = 0; i < products.size(); ++i)
            price_map[products[i]] = prices[i];
    }

    double getBill(vector<int>& product, vector<int>& amount) {
        count++;
        double total = 0;
        for (int i = 0; i < product.size(); ++i)
            total += price_map[product[i]] * amount[i];
        if (count % n == 0)
            total = total * (100 - discount) / 100.0;
        return total;
    }
};
      

class Cashier {
    int n, discount, count;
    Map<Integer, Integer> priceMap;

    public Cashier(int n, int discount, int[] products, int[] prices) {
        this.n = n;
        this.discount = discount;
        this.count = 0;
        priceMap = new HashMap<>();
        for (int i = 0; i < products.length; ++i) {
            priceMap.put(products[i], prices[i]);
        }
    }

    public double getBill(int[] product, int[] amount) {
        count++;
        double total = 0;
        for (int i = 0; i < product.length; ++i) {
            total += priceMap.get(product[i]) * amount[i];
        }
        if (count % n == 0) {
            total = total * (100 - discount) / 100.0;
        }
        return total;
    }
}
      

var Cashier = function(n, discount, products, prices) {
    this.n = n;
    this.discount = discount;
    this.count = 0;
    this.priceMap = {};
    for (let i = 0; i < products.length; ++i) {
        this.priceMap[products[i]] = prices[i];
    }
};

Cashier.prototype.getBill = function(product, amount) {
    this.count += 1;
    let total = 0;
    for (let i = 0; i < product.length; ++i) {
        total += this.priceMap[product[i]] * amount[i];
    }
    if (this.count % this.n === 0) {
        total = total * (100 - this.discount) / 100;
    }
    return total;
};