1357. Apply Discount Every n Orders

MediumDesignArrayHash Table

Problem Description

In this problem, we are asked to simulate the checkout process of a supermarket. There are two arrays, products and prices, representing the IDs and prices of all the products available in the supermarket, respectively. The checkout process involves a Cashier class that needs to be implemented with specific functionality. The class should handle customer bills where each bill is represented by two arrays, product and amount. The total bill or subtotal is calculated by multiplying the amount of each product by its price. Occasionally, a discount is applied to the subtotal if the customer is every nth customer. If a discount is applied, it is a percentage discount based on the discount value provided. The customer then only pays a fraction of the subtotal after the discount is taken into account. The Cashier class should be able to return the final amount the customer needs to pay, including any discounts.

Intuition

To solve the problem, the Cashier class is designed with an initialization method and a method to calculate the bill with a potential discount. During initialization, the Cashier object stores n, discount, and a dictionary mapping each product ID to its price. This setup is to efficiently look up the prices during bill computation.

The getBill method serves to compute the bill for each customer. A customer count i is maintained to track when to provide a discount (every nth customer). When calculating the subtotal, we look up the prices of each product in the provided dictionary. The bill is calculated by summing up the product of the amount and price of each item bought by the customer. If the customer is eligible for a discount (checked by seeing if i is divisible by n), the discount is applied to each item's total before adding it to the final bill. In the end, the method returns the final amount due, including any discount applied.

Solution Approach

The solution uses a simple object-oriented programming approach with a class Cashier that contains two methods: the constructor __init__, and getBill.

Constructor - `init`:

This method is used to initialize the cashier object. It takes the following parameters:

n: the frequency of the discount, indicating every nth customer receives a discount.
discount: the percentage of the discount applied to every nth customer's bill.
products: a list of integers representing the IDs of products.
prices: a list of integers representing the prices corresponding to the products by their index.

The constructor achieves the following:

It sets the instance variable self.i to 0, to keep track of the number of customers processed.
It stores n and discount in instance variables self.n and self.discount for use in the getBill method.
It creates a dictionary self.d that maps each product ID to its price for quick price lookup. This is accomplished by using the zip function to combine products and prices and converting the zipped object into a dictionary.

Method - `getBill`:

The getBill is responsible for calculating the total bill for a customer. It takes two arguments:

product: a list of integers representing the IDs of products in the customer's bill.
amount: a list of integers representing the quantities of the respective products in the customer's bill.

The method performs the following operations:

Increment the customer counter self.i.
Check if the current customer should get a discount by checking if the customer count self.i modulo n (self.i % self.n) is 0.
Initialize a variable ans to accumulate the bill total.
Iterate over the product and amount lists in parallel using zip.
For each item in the bill:
- Get the product price from the dictionary self.d.
- Calculate the price for the amount of the product.
- If the discount applies, reduce the price accordingly by multiplying by (100 - discount) / 100.
Add the calculated item price to the total ans.
Return the total ans, which represents the final bill amount.

By maintaining a customer count and using a dictionary for price lookup, the algorithm achieves efficient processing of each bill. The discount application is straightforward and only done every nth bill to avoid unnecessary checks and computations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with an example. We're given the following input:

n = 3 (every 3rd customer gets a discount)
discount = 10 (10% discount for the eligible customer)
products = [101, 102, 103, 104] (product IDs)
prices = [10, 15, 20, 25] (corresponding prices for product IDs)

First, we initialize the Cashier:

cashier = Cashier(n=3, discount=10, products=[101, 102, 103, 104], prices=[10, 15, 20, 25])

The Cashier object will track the number of customers in self.i, which starts at 0. It will also store our discount information and create a dictionary for product prices as self.d = {101: 10, 102: 15, 103: 20, 104: 25}.

Now let's simulate three customers checking out with their bills:

Customer 1 Buys:

product = [101, 102]
amount = [2, 1]

print(cashier.getBill(product=[101, 102], amount=[2, 1]))

For customer 1, self.i increments to 1. Since i % n is not 0, no discount is applied. The total is computed as 2 * 10 (for product 101) + 1 * 15 (for product 102), totaling 35.

Customer 2 Buys:

product = [103]
amount = [3]

print(cashier.getBill(product=[103], amount=[3]))

For customer 2, self.i increments to 2. Since i % n is not 0, no discount is applied. The total is 3 * 20 (for product 103), totaling 60.

Customer 3 Buys (eligible for discount):

product = [101, 104]
amount = [1, 2]

print(cashier.getBill(product=[101, 104], amount=[1, 2]))

For customer 3, self.i increments to 3. Since i % n is 0, this customer gets a discount. The total before discount is 1 * 10 (for product 101) + 2 * 25 (for product 104), which is 60. A 10% discount is applied, making the total 60 - (0.10 * 60) = 54.

So, for these three customers, the getBill method would return 35, 60, and 54, respectively. This demonstrates how the Cashier class processes customers' bills and applies discounts every nth customer.

Solution Implementation

1from typing import List
2
3class Cashier:
4    def __init__(self, n: int, discount: int, products: List[int], prices: List[int]):
5        # Initialize the counter to keep track of the number of customers
6        self.customer_count = 0
7        # Store the frequency of the discount application
8        self.discount_frequency = n
9        # Store the discount percentage
10        self.discount_percentage = discount
11        # Create a dictionary mapping products to their respective prices
12        self.product_prices = {product: price for product, price in zip(products, prices)}
13
14    def getBill(self, product: List[int], amount: List[int]) -> float:
15        # Increment the count of customers
16        self.customer_count += 1
17        # Check if the current customer is eligible for a discount
18        is_discounted = self.customer_count % self.discount_frequency == 0
19        # Initialize total bill amount
20        total_bill = 0
21      
22        # Calculate the bill by iterating over each product and its associated amount
23        for prod, amt in zip(product, amount):
24            # Calculate the total price for the product
25            total_price = self.product_prices[prod] * amt
26          
27            # If the customer is eligible for discount, apply it to the product price
28            if is_discounted:
29                total_price -= (self.discount_percentage * total_price) / 100
30          
31            # Add the total price for this product to the overall bill
32            total_bill += total_price
33          
34        # Return the final bill amount
35        return total_bill
36
37
38# Example on how to instantiate and call the Cashier class and getBill method:
39# cashier = Cashier(n, discount, products, prices)
40# bill = cashier.getBill(product, amount)
41

1import java.util.HashMap;
2import java.util.Map;
3
4class Cashier {
5    private int customerCount;       // Counts the number of customers served
6    private int nthCustomer;         // The nth customer who will get a discount
7    private int discountPercentage;  // The discount percentage
8    private Map<Integer, Integer> productPrices = new HashMap<>(); // Stores the product ID and price
9
10    /*
11     * Constructor for the Cashier class.
12     * @param nthCustomer: The number of customers after which the discount is applied.
13     * @param discountPercentage: The percentage of discount offered.
14     * @param products: A list of product IDs.
15     * @param prices: The corresponding prices of the products.
16     */
17    public Cashier(int nthCustomer, int discountPercentage, int[] products, int[] prices) {
18        this.nthCustomer = nthCustomer;
19        this.discountPercentage = discountPercentage;
20        // Initialize the productPrices map with the product IDs and their prices.
21        for (int i = 0; i < products.length; i++) {
22            productPrices.put(products[i], prices[i]);
23        }
24    }
25
26    /*
27     * Calculates the bill for the given customer.
28     * @param product: An array of product IDs that the customer is buying.
29     * @param amount:  The corresponding quantities of each product.
30     * @return The total bill for the customer considering possible discounts.
31     */
32    public double getBill(int[] product, int[] amount) {
33        customerCount++; // Increment the number of customers served
34        // Check if the current customer should receive a discount
35        int discountApplicable = (customerCount % nthCustomer == 0) ? discountPercentage : 0;
36        double total = 0.0; // Total bill initialized to 0
37      
38        // Calculate the bill
39        for (int i = 0; i < product.length; i++) {
40            int productId = product[i];
41            int productQuantity = amount[i];
42            int productPrice = productPrices.get(productId);
43            double cost = productPrice * productQuantity;
44            double discountedCost = cost - (discountApplicable * cost) / 100.0;
45            total += discountedCost; // Add the cost after discount to the total
46        }
47        return total; // Return the total bill
48    }
49}
50

1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Cashier {
6public:
7    // Constructor with initialization of the cashier system.
8    Cashier(int n, int discount, vector<int>& products, vector<int>& prices) {
9        customerCount = 0; // Initialize the customer counter.
10        this->checkoutFrequency = n; // Set the nth customer checkout frequency.
11        this->discountPercentage = discount; // Set the discount percentage.
12      
13        // Store the prices for each product.
14        for (int i = 0; i < products.size(); ++i) {
15            productPrices[products[i]] = prices[i];
16        }
17    }
18
19    // Method to calculate the bill for the current customer.
20    double getBill(vector<int> productIds, vector<int> productAmounts) {
21        customerCount++; // Increment customer count for each checkout.
22        // Check if the current customer is eligible for discount.
23        int isDiscountEligible = (customerCount % checkoutFrequency == 0) ? discountPercentage : 0;
24      
25        double totalCost = 0; // Initialize total cost of the bill.
26        // Calculate total cost of the current bill.
27        for (int j = 0; j < productIds.size(); ++j) {
28            int productPrice = productPrices[productIds[j]];
29            totalCost += productPrice * productAmounts[j];
30        }
31      
32        // Apply discount if the customer is eligible.
33        if (isDiscountEligible > 0) {
34            double discountAmount = (totalCost * isDiscountEligible) / 100.0;
35            totalCost -= discountAmount;
36        }
37      
38        return totalCost; // Return the final bill amount.
39    }
40
41private:
42    int customerCount; // Counter to track the number of customers served.
43    int checkoutFrequency; // The frequency at which a discount is given.
44    int discountPercentage; // The percentage of the discount applied.
45    unordered_map<int, int> productPrices; // Mapping from product ID to its price.
46};
47

1// Define the type for product pricing map.
2type ProductPriceMap = { [productId: number]: number };
3
4// Variables simulating the properties of the Cashier class
5let customerCount = 0; // Counter to track the number of customers served.
6let checkoutFrequency: number; // The frequency at which a discount is given.
7let discountPercentage: number; // The percentage of the discount applied.
8let productPrices: ProductPriceMap = {}; // Mapping from product ID to its price.
9
10// Function used for initializing the cashier system.
11function initializeCashier(n: number, discount: number, products: number[], prices: number[]): void {
12    customerCount = 0; // Resetting the customer counter.
13    checkoutFrequency = n; // Setting the nth customer checkout frequency.
14    discountPercentage = discount; // Setting the discount percentage.
15
16    // Storing the prices for each product.
17    productPrices = {}; // Resetting the product prices map.
18    products.forEach((productId, index) => {
19        productPrices[productId] = prices[index];
20    });
21}
22
23// Function to calculate the bill for the current customer.
24function getBill(productIds: number[], productAmounts: number[]): number {
25    customerCount++; // Increment the customer count for each checkout.
26    // Check if the current customer is eligible for a discount.
27    const isDiscountEligible: boolean = customerCount % checkoutFrequency === 0;
28
29    let totalCost = 0; // Initialize the total cost of the bill.
30
31    // Calculate the total cost of the current bill.
32    productIds.forEach((productId, index) => {
33        const productPrice = productPrices[productId];
34        totalCost += productPrice * productAmounts[index];
35    });
36
37    // Apply a discount if the customer is eligible.
38    if (isDiscountEligible) {
39        const discountAmount = (totalCost * discountPercentage) / 100;
40        totalCost -= discountAmount;
41    }
42
43    return totalCost; // Return the final bill amount.
44}
45

Time and Space Complexity

Time Complexity:

The time complexity of the __init__ method is O(m) where m is the number of products because we loop through each product-price pair to create a dictionary, which is a one-time set-up operation.

The getBill method has a time complexity of O(k) where k is the number of items in the product list corresponding to a customer's purchase, as we loop through each product-amount pair to calculate the cost.

Overall, when considering the getBill method, which will be called multiple times, the time complexity is dominated by O(k).

Space Complexity:

The space complexity of the __init__ method is also O(m) due to the dictionary storing product-price pairs.

The getBill method uses a constant amount of space, hence the space complexity is O(1).

Therefore, the overall space complexity, taking into account the dictionary created in the initializer, is O(m).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know