Problem Description

You need to implement a cashier system for a supermarket that tracks products and applies discounts to certain customers.

The supermarket has products with unique IDs and corresponding prices. These are given as two arrays:

• products[i] represents the ID of the i-th product
• prices[i] represents the price of the i-th product

When customers check out, their purchases are represented by:

• product[j] - the ID of the j-th product they're buying
• amount[j] - the quantity of the j-th product they're buying

The subtotal is calculated by summing up amount[j] * price for each product.

The supermarket runs a special promotion where every n-th customer receives a percentage discount. For example, if n = 3 and discount = 50, then the 3rd, 6th, 9th, etc. customers get 50% off their subtotal.

You need to implement a Cashier class with two methods:

1. Constructor Cashier(n, discount, products, prices): Initializes the cashier system with:

   • n: Every n-th customer gets the discount
   • discount: The discount percentage (0-100)
   • products and prices: Arrays defining the store's inventory

2. getBill (product, amount): Calculates and returns the final bill for a customer:

   • Takes arrays of product IDs and their quantities
   • Applies the discount if this is the n-th customer
   • Returns the final total as a float
   • The formula for discount is: final_price = subtotal * (100 - discount) / 100

The system needs to keep track of how many customers have been served to determine who gets the discount. Answers within 10^-5 of the actual value are accepted.

Intuition

The key insight is that we need to efficiently look up product prices and keep track of customer count to apply discounts at the right time.

Since we need to frequently look up prices by product ID when calculating bills, a hash table (dictionary) is the natural choice. This gives us O(1) price lookups instead of searching through the products array each time.

For tracking which customer gets the discount, we need a counter that increments with each customer. When counter % n == 0, we know this customer should receive the discount. This is a simple modulo operation that tells us if the current customer number is divisible by n.

The calculation flow becomes straightforward:

1. Increment the customer counter
2. Check if this customer gets a discount using counter % n
3. Calculate the subtotal by looking up each product's price in our hash table and multiplying by quantity
4. If there's a discount, apply it to each item as we calculate

The discount calculation can be done in two ways:

• Calculate the full subtotal first, then apply discount: subtotal * (100 - discount) / 100
• Apply discount to each item individually: price * amount * (100 - discount) / 100

Both approaches work, but applying the discount item by item as shown in the solution allows us to combine the calculation in a single pass through the products. The formula x - (discount * x) / 100 is mathematically equivalent to x * (100 - discount) / 100, where x is the item's cost before discount.

Solution Approach

The solution uses a hash table combined with simulation to efficiently handle product lookups and customer tracking.

Data Structure Setup:

• Create a hash table d that maps each product ID to its price: {product_id: price}
• Initialize a counter i to track the number of customers served
• Store the discount parameters n and discount for later use

Implementation Details:

1. Constructor (__init__):

   • Set self.i = 0 to track customer count
   • Store n and discount values
   • Build the hash table using dictionary comprehension: self.d = {product: price for product, price in zip(products, prices)}
   • The zip function pairs each product ID with its corresponding price

2. Bill Calculation (getBill):

   • Increment the customer counter: self.i += 1
   • Determine if current customer gets discount: discount = self.discount if self.i % self.n == 0 else 0
     • If i % n == 0, this is the n-th customer and gets the discount
     • Otherwise, discount is 0
   • Calculate the total bill:

     ans = 0
     for p, a in zip(product, amount):
         x = self.d[p] * a  # price * quantity
         ans += x - (discount * x) / 100  # apply discount if any

   • The formula x - (discount * x) / 100 calculates the discounted price
     • When discount = 0: result is x (no discount)
     • When discount > 0: result is x * (1 - discount/100) (discounted price)

Time Complexity:

• Constructor: O(m) where m is the number of products
• getBill: O(k) where k is the number of items in the current purchase

Space Complexity:

• O(m) to store the hash table of products and prices

Example Walkthrough

Let's walk through a concrete example to illustrate how the cashier system works.

Setup:

• Initialize: Cashier(n=3, discount=50, products=[1,2,3,4,5], prices=[100,200,300,400,500])
• This creates a hash table: {1:100, 2:200, 3:300, 4:400, 5:500}
• Customer counter starts at i=0
• Every 3rd customer gets 50% off

Customer 1:

• Call: getBill([1,2], [1,2])
• Counter increments: i=1
• Check discount: 1 % 3 = 1 (not divisible by 3, no discount)
• Calculate bill:
  • Product 1: 100 * 1 = 100
  • Product 2: 200 * 2 = 400
  • Total: 100 + 400 = 500.0

Customer 2:

• Call: getBill([3,5], [2,1])
• Counter increments: i=2
• Check discount: 2 % 3 = 2 (no discount)
• Calculate bill:
  • Product 3: 300 * 2 = 600
  • Product 5: 500 * 1 = 500
  • Total: 600 + 500 = 1100.0

Customer 3 (Gets Discount!):

• Call: getBill([1,2], [1,2])
• Counter increments: i=3
• Check discount: 3 % 3 = 0 (divisible by 3, apply 50% discount)
• Calculate bill with discount:
  • Product 1: 100 * 1 = 100, after discount: 100 - (50 * 100)/100 = 50
  • Product 2: 200 * 2 = 400, after discount: 400 - (50 * 400)/100 = 200
  • Total: 50 + 200 = 250.0 (half of the original 500)

Customer 4:

• Call: getBill([4], [3])
• Counter increments: i=4
• Check discount: 4 % 3 = 1 (no discount)
• Calculate bill:
  • Product 4: 400 * 3 = 1200
  • Total: 1200.0

Customer 6 (Gets Discount!):

• Would get 50% off since 6 % 3 = 0

This example demonstrates how the hash table provides instant price lookups and the modulo operation efficiently determines which customers receive discounts.

Solution Implementation

Time and Space Complexity

Time Complexity:

• Initialization (__init__): O(n), where n is the number of products. This is because creating the dictionary d requires iterating through the products and prices lists once using zip(), which takes linear time proportional to the number of products.

• getBill method: O(m), where m is the number of products being purchased (length of the product list in the method call). The method iterates through the product and amount lists once using zip(), and for each item, it performs constant time operations (dictionary lookup, multiplication, and arithmetic operations).

Space Complexity:

• O(n), where n is the number of products. The space is primarily consumed by the dictionary d that stores the mapping of all products to their prices. The dictionary contains n key-value pairs. Other variables (i, n, discount) use constant space O(1).

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

Common Pitfalls

1. Integer Division vs Float Division

A common mistake is using integer division when calculating the discount, which can lead to incorrect results in languages that distinguish between integer and float division.

Pitfall Example:

# Wrong - in Python 2 or some other languages, this could cause integer division
total_bill += subtotal - (discount_percentage * subtotal) // 100  # Using // instead of /

Solution: Always use float division and ensure the result is a float:

# Correct
total_bill += subtotal - (discount_percentage * subtotal) / 100
# Or explicitly convert to float
total_bill += subtotal * (100 - discount_percentage) / 100.0

2. Customer Counter Reset

Some implementations might accidentally reset the customer counter or fail to properly maintain state between calls.

Pitfall Example:

def getBill(self, product: List[int], amount: List[int]) -> float:
    customer_count = 0  # Wrong - creates local variable instead of using instance variable
    customer_count += 1
    # This will always treat every customer as the first customer

Solution: Always use the instance variable with self:

def getBill(self, product: List[int], amount: List[int]) -> float:
    self.customer_count += 1  # Correct - modifies instance variable

3. Incorrect Discount Formula Application

Applying the discount formula incorrectly, especially when mixing the percentage calculation.

Pitfall Example:

# Wrong - applies discount to each item individually before summing
for product_id, quantity in zip(product, amount):
    price = self.product_price_map[product_id]
    if self.customer_count % self.n == 0:
        price = price * (100 - self.discount) / 100  # Modifying price directly
    total_bill += price * quantity

Solution: Calculate the subtotal first, then apply discount to the total:

# Better approach - clearer logic
subtotal = sum(self.product_price_map[pid] * qty for pid, qty in zip(product, amount))
if self.customer_count % self.n == 0:
    return subtotal * (100 - self.discount) / 100
return subtotal

4. Missing Product ID in Hash Table

Not handling the case where a product ID might not exist in the hash table (though the problem assumes all product IDs are valid).

Pitfall Example:

# Could raise KeyError if product_id not in dictionary
subtotal = self.product_price_map[product_id] * quantity

Solution: Add defensive programming if needed:

# Defensive approach
subtotal = self.product_price_map.get(product_id, 0) * quantity
# Or with error handling
if product_id not in self.product_price_map:
    raise ValueError(f"Product {product_id} not found")

5. Precision Issues with Float Arithmetic

When dealing with money calculations, floating-point arithmetic can introduce precision errors.

Pitfall Example:

# Multiple float operations can accumulate rounding errors
for product_id, quantity in zip(product, amount):
    subtotal = self.product_price_map[product_id] * quantity
    discounted = subtotal - (discount_percentage * subtotal) / 100
    total_bill += discounted  # Accumulating potential rounding errors

Solution: Use the Decimal module for precise monetary calculations if needed:

from decimal import Decimal, ROUND_HALF_UP

# For precise monetary calculations
subtotal = Decimal(str(price)) * Decimal(str(quantity))
discount_amount = (subtotal * Decimal(str(discount_percentage)) / Decimal('100'))
final_amount = subtotal - discount_amount
# Round to 2 decimal places for currency
final_amount = final_amount.quantize(Decimal('0.01'), rounding=ROUND_HALF_UP)

However, since the problem accepts answers within 10^-5 of the actual value, regular float arithmetic is sufficient for this specific case.