Problem Breakdown
We are implementing a stateful system (Cashier) that manages supermarket billing with periodic discounts.
- Inputs: The constructor initializes the discount interval
n, percentagediscount, and product catalog (productsIDs,prices). The methodgetBillprocesses an order defined by specific products and amounts. - Outputs: A floating-point number representing the final bill amount after applying any applicable discount to the current customer’s total.
- State Management: This is a stateful problem requiring us to track how many customers have visited since initialization (
customer_count). The system must determine ifcustomer_countis divisible byn. - Data Lookup: Product IDs are integers up to 200 but not necessarily contiguous or sorted. Iterating through the product list for every order would be inefficient (). We need price lookups, suggesting a hash map (dictionary) approach where keys are product IDs and values are prices.
- Precision: Floating point arithmetic must handle standard LeetCode tolerances (
1e-5).
Intuition
A naive solution would scan the products array for every item in an order to find its price, resulting in per query where is the number of products. Given constraints (, calls ), this might pass but isn’t optimal if were larger or queries frequent.
- Key Insight: We can pre-process price information into a hash map during initialization to achieve constant-time lookups. Additionally, we maintain an instance variable
customer_countthat increments with every call togetBill. The discount logic is simply conditional on this counter modulo . - State Persistence: Since the problem implies a single cashier object handling multiple calls (as per LeetCode class structure), state must persist across method invocations.
Approach
- Initialization (
__init__):- Store
n,discount. - Construct a dictionary mapping each product ID directly to its price using the provided arrays during initialization (). This allows instant retrieval of costs during billing.
- Initialize
customer_count = 0to track visits.
- Store
- Billing Logic (
getBill):- Increment
customer_count. - Iterate through the current order list, summing up
(price * amount)for all items using dictionary lookup ( where is number of ordered items). - Check if the customer qualifies for discount:
if self.customer_count % n == 0. Note that we increment first to ensure the counter reflects the current visit. - If eligible, apply the formula:
bill = bill * (1 - discount / 100). Alternatively subtract(discount/100)*billfrom total. - Return the final calculated double value.
- Increment
Complexity Analysis
- Time Complexity:
- Constructor: where is the number of products to build the price map.
getBill: where is the length of the current order array (number of items ordered). Since we use a hash map for prices, lookup is amortized . Summing takes linear time relative to input size per call. Given constraints (, calls ), this is highly efficient.
- Space Complexity:
- to store the price map and state variables in memory.
Solution
from typing import List
class Cashier:
def __init__(self, n: int, discount: int, products: List[int], prices: List[int]):
self.n = n
self.discount = discount
# Map product ID to its price for O(1) lookup
self.price_map = {pid: p for pid, p in zip(products, prices)}
# Track the number of customers visited so far
self.customer_count = 0
def getBill(self, product: List[int], amount: List[int]) -> float:
self.customer_count += 1
raw_bill = 0.0
for pid, amt in zip(product, amount):
# Retrieve price from map and multiply by quantity ordered
raw_bill += self.price_map[pid] * amt
# Check if current customer is the n-th (or multiple of n)
if self.customer_count % self.n == 0:
# Apply discount percentage using multiplication for precision stability
raw_bill *= (1 - self.discount / 100.0)
return raw_bill
Edge Cases Handled
- Discount = 0: The logic
bill * (1 - 0/100)correctly returns the full bill without modification even if triggered by counter check. - Discount = 100: The formula results in a zero cost for eligible customers, which is handled naturally by float arithmetic.
- n = 1: Every customer will trigger
customer_count % 1 == 0, applying discount to every order correctly. - Missing Products: Constraints guarantee product IDs exist in the store list; however, dictionary lookups handle missing keys gracefully (though not expected per constraints).
- Large Amounts/Prices: Using floating point arithmetic (
floatin Python) handles values up to standard limits without overflow for this specific constraint range ( max bill), and precision is within accepted tolerance.