How do you solve Apply Discount Every n Orders on LeetCode?

Apply Discount Every n Orders (LeetCode #1357) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The optimal approach uses a dictionary (or hash map) to store product prices for O(1) lookups, significantly improving performance. It also maintains the customer count to apply discounts efficiently.

What is the brute force solution for Apply Discount Every n Orders?

The brute force approach for Apply Discount Every n Orders is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach calculates the total bill by iterating through each product in the customer's purchase and looking up the corresponding price. It checks if the customer is eligible for a discount based on their order count. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Apply Discount Every n Orders?

Apply Discount Every n Orders uses the following concepts: Array, Hash Table, Design. The recommended patterns to study are: .

#1357

Apply Discount Every n Orders

Medium

ArrayHash TableDesign

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a dictionary (or hash map) to store product prices for O(1) lookups, significantly improving performance. It also maintains the customer count to apply discounts efficiently.

⚙️

Algorithm

5 steps

1Step 1: Create a mapping of product IDs to their prices for quick access.
2Step 2: Initialize a customer count.
3Step 3: For each bill, calculate the total using the mapping.
4Step 4: Check if the customer count is divisible by n to apply the discount.
5Step 5: Return the final total.

solution.py13 lines

1class Cashier:
2    def __init__(self, n, discount, products, prices):
3        self.n = n
4        self.discount = discount
5        self.product_price = {products[i]: prices[i] for i in range(len(products))}
6        self.customer_count = 0
7
8    def getBill(self, product, amount):
9        self.customer_count += 1
10        total = sum(self.product_price[p] * a for p, a in zip(product, amount))
11        if self.customer_count % self.n == 0:
12            total *= (100 - self.discount) / 100
13        return total

ℹ

Complexity note: The time complexity is O(n) because we can look up product prices in constant time using a hash map, and we iterate through the purchased products once. The space complexity is O(n) due to storing product prices in the hash map.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.