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:

1. Increment the customer counter self.i.
2. 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.
3. Initialize a variable ans to accumulate the bill total.
4. Iterate over the product and amount lists in parallel using zip.
5. 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.
6. Add the calculated item price to the total ans.
7. 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.

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

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.