LeetCode 1357 - Apply Discount Every n Orders

LeetCode Problem 1357

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Design

Solution

Problem Understanding

The problem describes a supermarket that sells products identified by unique integer IDs. Each product has a corresponding price. Customers purchase products in certain amounts, generating a bill that is the sum of the prices multiplied by the amounts purchased. The supermarket offers a periodic discount: every nth customer gets a percentage discount off their subtotal.

The input consists of the parameters used to initialize a Cashier object: n (the interval for the discount), discount (percentage off), products (list of product IDs), and prices (list of prices corresponding to the product IDs). Then, a series of calls to getBill(product, amount) simulate customers checking out. The output is the final amount the customer pays, which applies the discount only if the customer is the nth one.

Constraints ensure that the product IDs are unique, purchase amounts are valid, and the number of calls is manageable. This guarantees that we do not have to handle invalid product IDs or duplicate products within a single bill, simplifying our implementation. Edge cases include zero discount, discount applied on the first customer if n=1, and handling multiple sequential calls correctly.

Approaches

The naive or brute-force approach would compute the subtotal by iterating through the purchased products for each getBill call. For every product in the product array, the code would search through the products array to find the corresponding price, multiply by the amount, sum the results, and then check if a discount applies. While correct, this approach requires a linear search for every product, making it inefficient if products is large.

The optimal approach leverages a hash map (dictionary) to map product IDs to prices during initialization. This allows for O(1) price lookups per product, avoiding repeated linear searches. A simple counter keeps track of the number of customers to determine when to apply the discount. This results in a time-efficient solution with straightforward logic.

Algorithm Walkthrough

1. Initialize Cashier Object: Store the discount interval n and discount percentage discount. Build a hash map price_map that maps each product ID to its price for O(1) lookups. Initialize a customer counter customer_count to 0.
2. Compute Bill in getBill: For each call to getBill, increment the customer counter by 1.
3. Calculate Subtotal: Iterate over the purchased product IDs. For each product ID, multiply the corresponding amount by the price retrieved from price_map and add it to a running subtotal.
4. Apply Discount If Applicable: If customer_count is divisible by n, multiply the subtotal by (100 - discount) / 100 to apply the discount. Otherwise, the subtotal remains unchanged.
5. Return Final Bill: Return the resulting total as a floating-point number.

Why it works: The hash map ensures constant-time price lookup, so we avoid repeated searches. Incrementing the counter guarantees that the discount is applied exactly every nth customer. The algorithm correctly handles any number of calls in sequence and applies the discount accurately based on the customer order.

Python 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
        self.price_map = {prod: price for prod, price in zip(products, prices)}
        self.customer_count = 0

    def getBill(self, product: List[int], amount: List[int]) -> float:
        self.customer_count += 1
        subtotal = 0
        for prod_id, amt in zip(product, amount):
            subtotal += self.price_map[prod_id] * amt
        if self.customer_count % self.n == 0:
            subtotal *= (100 - self.discount) / 100
        return subtotal

In this Python implementation, we first create a mapping of product IDs to their prices for quick lookups. Each call to getBill updates the customer count and calculates the subtotal using this mapping. The discount is conditionally applied based on the counter, and the final subtotal is returned as a floating-point number, which meets the precision requirement of 10^-5.

Go Solution

type Cashier struct {
	n            int
	discount     int
	priceMap     map[int]int
	customerCount int
}

func Constructor(n int, discount int, products []int, prices []int) Cashier {
	priceMap := make(map[int]int)
	for i, prod := range products {
		priceMap[prod] = prices[i]
	}
	return Cashier{
		n:            n,
		discount:     discount,
		priceMap:     priceMap,
		customerCount: 0,
	}
}

func (this *Cashier) GetBill(product []int, amount []int) float64 {
	this.customerCount++
	subtotal := 0
	for i, prodID := range product {
		subtotal += this.priceMap[prodID] * amount[i]
	}
	if this.customerCount%this.n == 0 {
		return float64(subtotal) * float64(100-this.discount) / 100.0
	}
	return float64(subtotal)
}

The Go implementation mirrors the Python solution. A map provides constant-time lookups for product prices. Care is taken to cast integers to float64 when applying the discount to ensure proper floating-point division. The customer counter and discount logic remain identical.

Worked Examples

Consider the first example: Cashier(3, 50, [1,2,3,4,5,6,7], [100,200,300,400,300,200,100]).

Complexity Analysis

Using a hash map reduces repeated searches and ensures that each getBill call runs in linear time relative to the number of products in that bill.

Test Cases

# Provided examples
cashier = Cashier(3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100])
assert abs(cashier.getBill([1,2],[1,2]) - 500.0) < 1e-5
assert abs(cashier.getBill([3,7],[10,10]) - 4000.0) < 1e-5
assert abs(cashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]) - 800.0) < 1e-5
assert abs(cashier.getBill([4],[10]) - 4000.0) < 1e-5
assert abs(cashier.getBill([7,3],[10,10]) - 4000.0) < 1e-5
assert abs(cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]) - 7350.0) < 1e-5
assert abs(cashier.getBill([2,3,5],[5,3,2]) - 2500.0) < 1e-5

# Edge cases
cashier = Cashier(1,100,[1],[100