Apply Discount Every n Orders: Design with Hash Map

Apply Discount Every n Orders is LeetCode 1357. You need to design a cashier system for a supermarket. The system tracks how many customers have been served. Every nth customer gets a percentage discount on their entire bill.

You are given a list of products and their prices. Each time a customer checks out, you look up the price of each product they are buying, multiply by the quantity, and sum it all up. If this customer is the nth, 2nth, 3nth, and so on, you apply the discount before returning the total.

The approach

There are two things to manage here: price lookup and discount tracking.

For price lookup, the most natural choice is a hash map. You receive parallel arrays of product IDs and prices. Zip them together into a dictionary, and every future price lookup becomes O(1). No searching, no scanning.

For discount tracking, you keep a simple counter. Every time getBill is called, increment the counter. If the counter is divisible by n, apply the discount. That is the entire logic. No need for a queue, no need to store customer history, no cyclic buffer. Just one integer and a modulo check.

The discount itself is a percentage reduction. If the discount is 50%, you multiply the total by (100 - 50) / 100 = 0.5. This works for any discount value from 0 to 100.

The solution

class Cashier:
    def __init__(self, n: int, discount: int, products: list[int], prices: list[int]):
        self.n = n
        self.discount = discount
        self.price_map = dict(zip(products, prices))
        self.count = 0

    def get_bill(self, product: list[int], amount: list[int]) -> float:
        self.count += 1
        total = sum(self.price_map[p] * a for p, a in zip(product, amount))
        if self.count % self.n == 0:
            total *= (100 - self.discount) / 100
        return total

Breaking down the solution

__init__: The constructor takes n (every nth customer gets a discount), discount (percentage off), and the product catalog as two parallel lists. The key line is dict(zip(products, prices)), which pairs each product ID with its price and builds a lookup dictionary in one pass. We also initialize a counter at zero.

get_bill: Each call increments the counter first. Then it computes the raw total by looking up each product in the price map, multiplying by the quantity, and summing. Finally, if the counter is a multiple of n, it scales the total down by the discount percentage. The result is returned as a float.

The zip(product, amount) inside the generator expression pairs each product with its quantity, so you iterate through them together without needing index variables.

Visual walkthrough

Let's trace through five customer interactions with n = 3, discount = 50, and products {1: $100, 2: $200, 3: $300}. Watch how only the 3rd customer gets the discount.

Notice the pattern: customers 1 and 2 pay full price, customer 3 gets the discount, then customers 4 and 5 pay full price again. The next discount would hit customer 6, then 9, then 12, and so on. The modulo operation handles this cycle automatically.

Complexity analysis

Time: each getBill call iterates through the m products in that particular order, doing an O(1) dictionary lookup for each. So the time per call is O(m), where m is the number of distinct products in a single transaction.

Space: the price map stores all p products from the catalog. The counter and discount values are O(1). Total space is O(p).

Building blocks

This problem exercises two patterns that appear frequently in design questions.

Hash map for catalog lookup. Anytime you are given a mapping between IDs and values, build a dictionary up front. This converts repeated linear scans into constant-time lookups:

price_map = dict(zip(products, prices))
cost = price_map[product_id]

Counter with modulo for periodic events. When something should happen every n steps, a counter plus count % n == 0 is the cleanest approach. No need for timers, flags, or reset logic:

self.count += 1
if self.count % self.n == 0:
    total *= (100 - self.discount) / 100

Edge cases

• discount = 0. The formula total *= (100 - 0) / 100 simplifies to total *= 1.0, so the bill is unchanged. No special handling needed.
• Single product per order. The sum contains just one term. The logic is identical, just a shorter loop.
• Large n. If n is 1000, the first 999 customers pay full price. The counter still works. You just wait longer between discounts.
• n = 1. Every single customer gets the discount, because every positive integer is a multiple of 1. The modulo check passes every time.

From understanding to recall

This is the kind of problem that feels almost too simple once you see the solution. A dictionary, a counter, and a modulo check. But that simplicity is deceptive. Under interview pressure, you might second-guess yourself. Should you use a queue? Do you need to reset the counter? Is the discount applied before or after summing?

Spaced repetition removes that uncertainty. You type the solution from scratch, and the system schedules your next review right before you would forget it. After a few reps, the dict(zip(...)) pattern and the modulo discount become automatic. You stop thinking about the mechanics and start thinking about edge cases and follow-up questions.

Related posts

• Design HashMap - Build a hash map from scratch, the same data structure powering the price lookup in this problem
• LRU Cache - Another design problem that pairs a hash map with a secondary structure for O(1) operations
• Design Twitter - A more complex design problem that layers multiple data structures together

---

If you found this walkthrough helpful, try solving it yourself on CodeBricks. The platform schedules your reviews so you retain what you learn, not just understand it once.