Leetcode 1357. Apply Discount Every n Orders

Problem Explanation

In this problem, we need to implement a system for a supermarket which gives discount to every nth customer. The supermarket sells certain products, each with a unique id and respective price. When a customer arrives, the system calculates the total bill depending on the products and their quantities ordered by the customer. If the customer is the nth customer, the discount is applied to the total bill. The discount is calculated by first calculating the discount amount (total bill * discount / 100) and then subtracting it from the total bill. We need to implement the system with these functionalities.

Example: Suppose we initialize the system with n = 3, discount = 50, products = [1,2,3,4,5,6,7], prices = [100,200,300,400,300,200,100]. A customer arrives and orders product = [1,2], amount = [1,2]. The system calculates the total bill as 1 * 100 + 2 * 200 = 500 and returns it. Then another customer arrives and orders product = [3,7], amount = [10,10]. The system calculates the total bill as 10 * 300 + 10 * 100 = 4000 and returns it. Now, the next customer arrives and orders product = [1,2,3,4,5,6,7] and amount = [1,1,1,1,1,1,1]. The total bill before discount is 1 * 100 + 1 * 200 + 1 * 300 + 1 * 400 + 1 * 300 + 1 * 200 + 1 * 100 = 1600. But as this customer is the third customer, a discount of 50% is applied and the final total bill becomes 1600 - 1600 * 50/100 = 800.

Walkthrough to Solution

To solve the problem, we can create a Cashier class to represent the system. This class will have private attributes to remember the discount rate, the number of customers after which the discount should be applied, a mapping of the products to their prices, and a counter for the current number of customers.

Whenever a getBill function is called, we increment the customer count and iterate through the products ordered by the customer to calculate the total bill. If the customer count is a multiple of n, we apply the discount to the total bill before returning it.

To check if the customer count is a multiple of n, we can use the modulus operator (%). As for applying the discount, note that the discount is expressed as a percentage, so we need to divide it by 100 to get the discount fraction. Also, if we want to subtract the discount from the total, we can equivalently multiply the total by 1 - discount / 100.

Algorithms/Patterns Used

  1. Simple mathematics for calculating total bill and applying discount.
  2. Modulus operator for handling nth customer.
  3. unordered_map as lookup table for products and prices.

C# Implementation

1
2csharp
3public class Cashier {
4    private int n, discount, count;
5    private Dictionary<int, int> productToPrice;
6    public Cashier(int n, int discount, int[] products, int[] prices) {
7        this.n = n;
8        this.discount = discount;
9        this.productToPrice = new Dictionary<int, int>();
10        for (int i = 0; i < products.Length; i++)
11            this.productToPrice[products[i]] = prices[i];
12    }
13    
14    public double GetBill(int[] product, int[] amount) {
15        ++count;
16        int total = 0;
17        //calculate total bill
18        for (int i = 0; i < product.Length; i++)
19            total += productToPrice[product[i]] * amount[i];
20        //apply discount if necessary
21        return count % n == 0 ? total * (1 - discount / 100.0) : total;
22    }
23}

Python Implementation

1
2python
3from collections import defaultdict
4
5class Cashier:
6    def __init__(self, n: int, discount: int, products: List[int], prices: List[int]):
7        self.n = n
8        self.discount = discount
9        self.productToPrice = defaultdict(int,{product: price for product,price in zip(products,prices)})
10        self.count = 0
11    
12    def getBill(self, product: List[int], amount: List[int]) -> float:
13        self.count += 1
14        total = sum(self.productToPrice[prod] * amt for prod, amt in zip(product, amount))
15        return total if self.count % self.n != 0 else total * (1 - self.discount / 100)

Java Implementation

1
2java
3import java.util.*;
4
5class Cashier {
6  int n, discount, count;
7  HashMap<Integer, Integer> productToPrice;
8
9  public Cashier(int n, int discount, int[] products, int[] prices) {
10    this.n = n;
11    this.discount = discount;
12    this.count = 0;
13    this.productToPrice = new HashMap<Integer, Integer>();
14    for (int i = 0; i < products.length; i++)
15      this.productToPrice.put(products[i], prices[i]);
16  }
17    
18  public double getBill(int[] product, int[] amount) {
19    ++count;
20    int total = 0;
21    for (int i = 0; i < product.length; i++)
22      total += productToPrice.get(product[i]) * amount[i];
23    return count % n == 0 ? total * (1 - discount / 100.0) : total;
24  }
25}

Javascript Implementation

1
2javascript
3class Cashier {
4    constructor(n, discount, products, prices) {
5        this.n = n;
6        this.discount = discount;
7        this.count = 0;
8        this.productToPrice = {};
9        for(let i = 0; i < products.length; i++) {
10            this.productToPrice[products[i]] = prices[i];   
11        }
12    }
13    
14    getBill(product, amount) {
15        this.count++;
16        let total = 0;
17        for(let i = 0; i < product.length; i++) {
18            total += this.productToPrice[product[i]] * amount[i];   
19        }
20        return this.count % this.n === 0 ? total * (1 - this.discount / 100) : total;
21    }
22}

C++ Implementation

1
2cpp
3class Cashier {
4public:
5    Cashier(int n, int discount, vector<int>& products, vector<int>& prices)
6        : n(n), discount(discount), count(0) {
7        for (int i = 0; i < products.size(); ++i)
8            productToPrice[products[i]] = prices[i];
9    }
10    
11    double getBill(vector<int> product, vector<int> amount) {
12        ++count;
13        int total = 0;
14        for (int i = 0; i < product.size(); ++i)
15            total += productToPrice[product[i]] * amount[i];
16        return count % n == 0 ? total * (1 - discount / 100.0) : total;
17    }
18
19private:
20  int n, discount, count;
21  unordered_map<int, int> productToPrice;
22}

Ruby Implementation

1
2ruby
3class Cashier
4  def initialize(n, discount, products, prices)
5    @n = n
6    @discount = discount
7    @count = 0
8    @product_to_price = {
9      products.zip(prices).to_h
10    }
11  end
12
13  def get_bill(products, amounts)
14    @count += 1
15    total = 0
16    products.each_index do |i|
17      total += @product_to_price[products[i]] * amounts[i]
18    end
19    return @count % @n == 0 ? total * (1 - @discount / 100.0) : total
20  end
21end

In the Ruby version, we create a new Cashier class and then define an initialize method which is similar to constructors in other languages. We use instance variables to keep track of system parameters like n, discount and the products and their prices through @product_to_price. We also keep track of the current customer count with @count.

The get_bill method iterates through each product ordered by the customer, retrieves its price from @product_to_price, multiplies it with the corresponding ordered quantity, and adds the result to the total. If the current customer count is a multiple of @n, the total bill is reduced by the given discount percentage.

Swift Implementation

1
2swift
3class Cashier {
4    var n: Int
5    var discount: Int
6    var count: Int = 0
7    var productToPrice = [Int: Int]()
8
9    init(_ n: Int, _ discount: Int, _ products: [Int], _ prices: [Int]) {
10        self.n = n
11        self.discount = discount
12        for i in 0..<products.count {
13            productToPrice[products[i]] = prices[i]
14        }
15    }
16
17    func getBill(_ product: [Int], _ amount: [Int]) -> Double {
18        count += 1
19        var total = 0
20        for i in 0..<product.count {
21            total += productToPrice[product[i]]! * amount[i]
22        }
23        return count % n == 0 ? Double(total) * (1 - Double(discount) / 100.0) : Double(total)
24    }
25}

In the Swift version, we create a new class called Cashier. The init method is similar to the __init__ method in Python or the constructor in Java. We also use a dictionary to store the products and their respective prices.

In the getBill method, we first increment the number of customers. We then iterate through each product ordered and calculate the total price, taking the quantity into account. If the customer count is divisible by n, we apply the discount by multiplying the total by (1 - discount / 100.0).

In all these versions, it is important to note the use of dictionaries (or equivalents) and simple mathematics to calculate total bill, apply discount and handle nth customer.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫