Domain 2MediumMEDIUM

Apply Discount Every n Orders

Track customer count to apply discount every nth call using a hash map for O(1) price lookups.

Domain: medium•Updated: 2026-09-15
#simulation#hash-map#O(K)#O(P)

Problem Breakdown

We are implementing a stateful system (Cashier) that manages supermarket billing with periodic discounts.

  • Inputs: The constructor initializes the discount interval n, percentage discount, and product catalog (products IDs, prices). The method getBill processes 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 if customer_count is divisible by n.
  • 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 (O(P)O(P)). We need O(1)O(1) 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 O(P)O(P) per query where PP is the number of products. Given constraints (P≤200P \le 200, calls ≤1000\le 1000), this might pass but isn’t optimal if PP 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_count that increments with every call to getBill. The discount logic is simply conditional on this counter modulo nn.
  • 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

  1. Initialization (__init__):
    • Store n, discount.
    • Construct a dictionary mapping each product ID directly to its price using the provided arrays during initialization (O(P)O(P)). This allows instant retrieval of costs during billing.
    • Initialize customer_count = 0 to track visits.
  2. Billing Logic (getBill):
    • Increment customer_count.
    • Iterate through the current order list, summing up (price * amount) for all items using dictionary lookup (O(K)O(K) where KK 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)*bill from total.
    • Return the final calculated double value.

Complexity Analysis

  • Time Complexity:
    • Constructor: O(P)O(P) where PP is the number of products to build the price map.
    • getBill: O(K)O(K) where KK is the length of the current order array (number of items ordered). Since we use a hash map for prices, lookup is amortized O(1)O(1). Summing takes linear time relative to input size per call. Given constraints (P≤200P \le 200, calls ≤1000\le 1000), this is highly efficient.
  • Space Complexity:
    • O(P)O(P) 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 (float in Python) handles values up to standard limits without overflow for this specific constraint range (10810^8 max bill), and precision is within accepted tolerance.