{x}
blog image

Apply Discount Every n Orders

There is a supermarket that is frequented by many customers. The products sold at the supermarket are represented as two parallel integer arrays products and prices, where the ith product has an ID of products[i] and a price of prices[i].

When a customer is paying, their bill is represented as two parallel integer arrays product and amount, where the jth product they purchased has an ID of product[j], and amount[j] is how much of the product they bought. Their subtotal is calculated as the sum of each amount[j] * (price of the jth product).

The supermarket decided to have a sale. Every nth customer paying for their groceries will be given a percentage discount. The discount amount is given by discount, where they will be given discount percent off their subtotal. More formally, if their subtotal is bill, then they would actually pay bill * ((100 - discount) / 100).

Implement the Cashier class:

  • Cashier(int n, int discount, int[] products, int[] prices) Initializes the object with n, the discount, and the products and their prices.
  • double getBill(int[] product, int[] amount) Returns the final total of the bill with the discount applied (if any). Answers within 10-5 of the actual value will be accepted.

 

Example 1:

Input
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
Output
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]
Explanation
Cashier cashier = new Cashier(3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]);
cashier.getBill([1,2],[1,2]);                        // return 500.0. 1st customer, no discount.
                                                     // bill = 1 * 100 + 2 * 200 = 500.
cashier.getBill([3,7],[10,10]);                      // return 4000.0. 2nd customer, no discount.
                                                     // bill = 10 * 300 + 10 * 100 = 4000.
cashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]);    // return 800.0. 3rd customer, 50% discount.
                                                     // Original bill = 1600
                                                     // Actual bill = 1600 * ((100 - 50) / 100) = 800.
cashier.getBill([4],[10]);                           // return 4000.0. 4th customer, no discount.
cashier.getBill([7,3],[10,10]);                      // return 4000.0. 5th customer, no discount.
cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); // return 7350.0. 6th customer, 50% discount.
                                                     // Original bill = 14700, but with
                                                     // Actual bill = 14700 * ((100 - 50) / 100) = 7350.
cashier.getBill([2,3,5],[5,3,2]);                    // return 2500.0.  7th customer, no discount.

 

Constraints:

  • 1 <= n <= 104
  • 0 <= discount <= 100
  • 1 <= products.length <= 200
  • prices.length == products.length
  • 1 <= products[i] <= 200
  • 1 <= prices[i] <= 1000
  • The elements in products are unique.
  • 1 <= product.length <= products.length
  • amount.length == product.length
  • product[j] exists in products.
  • 1 <= amount[j] <= 1000
  • The elements of product are unique.
  • At most 1000 calls will be made to getBill.
  • Answers within 10-5 of the actual value will be accepted.

Solution Explanation:

This problem requires designing a Cashier class to manage customer bills and apply discounts every n orders. The solution uses a hash table (dictionary in Python, HashMap in Java, unordered_map in C++, map in Go) for efficient lookup of product prices.

Approach:

  1. Initialization (__init__ or Constructor): The constructor initializes the Cashier object. It takes the discount frequency (n), discount percentage (discount), product IDs (products), and corresponding prices (prices) as input. It creates a hash table (d) to store product IDs as keys and their prices as values, enabling O(1) lookup during bill calculation. It also initializes a counter (i) to track the number of customers served, starting at 0.

  2. Bill Calculation (getBill): The getBill method calculates the total bill for a customer.

    • It increments the customer counter (i).
    • It checks if the current customer (i) is a multiple of n. If it is, a discount is applied; otherwise, no discount is applied.
    • It iterates through the customer's purchased products (product) and their quantities (amount). For each product, it looks up its price in the hash table (d), calculates the cost of that product, and adds it to the total bill (ans).
    • If a discount applies, it reduces the total bill (ans) accordingly.
    • Finally, it returns the total bill.

Time and Space Complexity:

  • Time Complexity:

    • Initialization: O(p), where p is the number of products. This is due to the creation of the hash table.
    • getBill: O(m), where m is the number of products in the customer's order. This is due to iterating through the customer's products to calculate the bill.

  • Space Complexity: O(p), where p is the number of products. This is due to the space used by the hash table to store product prices.

Code Implementation (with explanations):

The code in different languages is provided in the previous response. Here's a breakdown focusing on key aspects:

  • Hash Table Usage: The hash table is crucial for efficient price lookups. Instead of iterating through the products and prices arrays each time a product's price is needed, the hash table provides O(1) average-case lookup time.

  • Discount Application: The conditional statement discount = self.discount if self.i % self.n == 0 else 0 elegantly handles the discount application. The modulo operator (%) efficiently checks if the customer number is a multiple of n.

  • Error Handling: The code implicitly handles cases where a product in the customer's order is not found in the d (hash table). A more robust version might include explicit error handling (e.g., raising an exception).

This solution efficiently handles the problem's requirements by leveraging the properties of hash tables for quick price lookups, resulting in an optimal time complexity for both initialization and bill calculation.