1357. Apply Discount Every n Orders
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 n
th 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 n
th 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 everyn
th 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
to0
, to keep track of the number of customers processed. - It stores
n
anddiscount
in instance variablesself.n
andself.discount
for use in thegetBill
method. - It creates a dictionary
self.d
that maps each product ID to its price for quick price lookup. This is accomplished by using thezip
function to combineproducts
andprices
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
modulon
(self.i % self.n
) is0
. - Initialize a variable
ans
to accumulate the bill total. - Iterate over the
product
andamount
lists in parallel usingzip
. - 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
.
- Get the product price from the dictionary
- 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 n
th 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 EvaluatorExample 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 n
th 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.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!