Apply Discount Every n Orders - Solution & Explanation

Q: Is Apply Discount Every n Orders easy or hard?

Apply Discount Every n Orders is typically rated Medium difficulty. The logic itself is straightforward, but the problem checks whether you can design a class that maintains state across calls and uses efficient lookups to compute totals correctly.

Q: Apply Discount Every n Orders Python/Java solution

In Python or JavaScript, a dictionary or object map stores product prices for constant-time lookup. In Java or C++, many implementations use an array indexed by product ID for faster access when IDs are bounded. Both implementations compute each bill in O(k) time.

Q: How to solve Apply Discount Every n Orders in O(n)?

Maintain a price lookup structure such as a hash map or array and keep a running order counter. For each bill request, iterate through the product list once, accumulate the total cost, and apply the discount when the order number is divisible by n. The computation is linear in the number of ordered items, giving O(k) time per order.

Q: What is the best approach for Apply Discount Every n Orders?

The most practical approach uses a hash map to store product ID to price mappings and an internal counter to track how many customers have been served. Each call to getBill iterates through the ordered products, multiplies price by quantity, and applies the discount when orderCount % n == 0. This keeps each order calculation O(k), where k is the number of items in the order.

Q: Is Apply Discount Every n Orders asked at Google/Amazon/Meta?

This problem belongs to the design category commonly seen in interviews at companies like Amazon and Google. It tests the ability to design a class with persistent state, perform efficient lookups, and handle repeated method calls with conditional logic.

Q: What data structure is used in Apply Discount Every n Orders?

The core data structure is a hash table or array used to map product IDs to their prices. A simple integer counter tracks how many customers have been processed so far so the system can apply the discount every n-th order.

Q: What is the time complexity of Apply Discount Every n Orders?

The time complexity per getBill call is O(k), where k is the number of products in the current order. Each product requires a constant-time lookup for its price and a multiplication with its quantity. Initialization takes O(P) to store the product-price mapping.

MediumArray Hash Table Design12 min readAsked at: Meta

Practice this problem

Problem Statement

There is a supermarket that is frequented by many customers. The products sold at the supermarket are represented as two parallel integer arrays products and prices, where the i^th product has an ID of products[i] and a price of prices[i].

When a customer is paying, their bill is represented as two parallel integer arrays product and amount, where the j^th product they purchased has an ID of product[j], and amount[j] is how much of the product they bought. Their subtotal is calculated as the sum of each amount[j] * (price of the j^th product).

The supermarket decided to have a sale. Every n^th customer paying for their groceries will be given a percentage discount. The discount amount is given by discount, where they will be given discount percent off their subtotal. More formally, if their subtotal is bill, then they would actually pay bill * ((100 - discount) / 100).

Implement the Cashier class:

Cashier(int n, int discount, int[] products, int[] prices) Initializes the object with n, the discount, and the products and their prices.
double getBill(int[] product, int[] amount) Returns the final total of the bill with the discount applied (if any). Answers within 10^-5 of the actual value will be accepted.

Example 1:

Input
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
Output
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]
Explanation
Cashier cashier = new Cashier(3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]);
cashier.getBill([1,2],[1,2]);                        // return 500.0. 1^st customer, no discount.
                                                     // bill = 1 * 100 + 2 * 200 = 500.
cashier.getBill([3,7],[10,10]);                      // return 4000.0. 2^nd customer, no discount.
                                                     // bill = 10 * 300 + 10 * 100 = 4000.
cashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]);    // return 800.0. 3^rd customer, 50% discount.
                                                     // Original bill = 1600
                                                     // Actual bill = 1600 * ((100 - 50) / 100) = 800.
cashier.getBill([4],[10]);                           // return 4000.0. 4^th customer, no discount.
cashier.getBill([7,3],[10,10]);                      // return 4000.0. 5^th customer, no discount.
cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); // return 7350.0. 6^th customer, 50% discount.
                                                     // Original bill = 14700, but with
                                                     // Actual bill = 14700 * ((100 - 50) / 100) = 7350.
cashier.getBill([2,3,5],[5,3,2]);                    // return 2500.0.  7^th customer, no discount.

Constraints:

1 <= n <= 10⁴
0 <= discount <= 100
1 <= products.length <= 200
prices.length == products.length
1 <= products[i] <= 200
1 <= prices[i] <= 1000
The elements in products are unique.
1 <= product.length <= products.length
amount.length == product.length
product[j] exists in products.
1 <= amount[j] <= 1000
The elements of product are unique.
At most 1000 calls will be made to getBill.
Answers within 10^-5 of the actual value will be accepted.

Approach Overview

Problem Overview: Design a cashier system that calculates the bill for customer orders. Each order contains product IDs and quantities. Every n-th customer receives a percentage discount on the total bill. The challenge is maintaining product prices and efficiently computing each order’s cost while tracking when the discount should be applied.

Approach 1: HashMap for Product Prices (Time: O(k) per order, Space: O(P))

Store product prices in a hash map where the key is the product ID and the value is its price. When getBill is called, iterate through the product list, perform a constant-time hash lookup for each price, multiply by the corresponding amount, and accumulate the total. Maintain an internal order counter. If the counter is divisible by n, apply the discount percentage to the computed bill. This approach works well when product IDs are sparse or not guaranteed to be contiguous. The hash lookup keeps price retrieval efficient and keeps the overall order processing time proportional to the number of products in the order.

This method relies heavily on constant-time lookups from a hash table. It fits naturally with problems that require quick key-based access and flexible product identifiers. In most real-world systems where product IDs may be arbitrary, this approach is the most practical.

Approach 2: Index Mapping with Arrays (Time: O(k) per order, Space: O(P))

If product IDs fall within a predictable numeric range, an array can replace the hash map. Use the product ID as the direct index in the array and store its price at that position. During billing, iterate through the ordered products and fetch prices using direct array indexing, which is slightly faster than hashing due to lower overhead.

The rest of the logic remains identical: increment the order counter, compute the total by multiplying price and quantity for each product, and apply the discount when orderCount % n == 0. This technique uses the strengths of arrays for constant-time access and minimal memory overhead when IDs are dense. It also keeps the implementation simple in languages where arrays are the default structure.

Because the problem focuses on maintaining internal state across calls, it also falls under classic design problems where the object must efficiently manage data and operations over time.

Recommended for interviews: The hash map approach is usually the expected solution. It handles arbitrary product IDs and clearly demonstrates understanding of constant-time lookups and stateful class design. Showing the array mapping optimization afterward highlights awareness of performance tradeoffs when IDs are bounded.

Approach 1: Hashmap for Product Prices

In this approach, we can use a hashmap (dictionary) to store the product IDs with their corresponding prices. This way, we can easily retrieve the price of a product using its ID in constant time.

For each call to getBill, we increment a counter. If the counter reaches n, we apply the discount to the subtotal calculated. Otherwise, we return the subtotal as it is.

The Cashier class is initialized with the number of customers to apply discount (n), the discount percentage, and lists of product IDs and their respective prices. During initialization, a hashmap (price_map) is created to store product IDs as keys and their prices as values. The getBill method is called each time a customer checks out, incrementing the customer counter. If the counter equals n, the discount is applied to the subtotal, otherwise the subtotal is returned without discount.

Code

Python JavaScript

Python

JavaScript

Complexity

Time Complexity: O(m), where m is the number of different products in the customer's list.
Space Complexity: O(k), where k is the number of unique products in the store.

Try this approach in the editor →

Approach 2: Index Mapping with Arrays

This approach utilizes two arrays, one for storing IDs and another for their prices, to efficiently access the prices by indexing. This method is optimized for scenarios where products are frequently added and their prices queried.

The operation involves maintaining a counter for the customer number and applying a discount only when the counter reaches the specified n.

In this C++ implementation, the Cashier class initializes with the customer frequency n, the discount percentage, and the product data. A hashmap stores product IDs and prices. For each getBill call, the subtotal is computed and a discount applied every n-th customer.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(m), where m is the number of different products in the customer's list.
Space Complexity: O(k), where k is the number of unique products in the store.

Try this approach in the editor →

Approach 3: Hash Table + Simulation

Use a hash table d to store the product ID and price, then traverse the product ID and quantity, calculate the total price, and then calculate the price after discount based on the discount.

The time complexity of initialization is O(n), where n is the number of products. The time complexity of the getBill function is O(m), where m is the number of products purchased. The space complexity is O(n).

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Hashmap for Product Prices	Time Complexity: O(m), where m is the number of different products in the customer's list. Space Complexity: O(k), where k is the number of unique products in the store.
Index Mapping with Arrays	Time Complexity: O(m), where m is the number of different products in the customer's list. Space Complexity: O(k), where k is the number of unique products in the store.
Hash Table + Simulation	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
HashMap for Product Prices	O(k) per order	O(P)	General case when product IDs may be sparse or non-contiguous
Index Mapping with Arrays	O(k) per order	O(P)	When product IDs fall within a small bounded range and direct indexing is possible

Video Solution

Apply Discount Every n Orders (Leetcode 1357) • Coding Interviews • 259 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Apply Discount Every n Orders easy or hard?

Apply Discount Every n Orders is typically rated Medium difficulty. The logic itself is straightforward, but the problem checks whether you can design a class that maintains state across calls and uses efficient lookups to compute totals correctly.

Apply Discount Every n Orders Python/Java solution

In Python or JavaScript, a dictionary or object map stores product prices for constant-time lookup. In Java or C++, many implementations use an array indexed by product ID for faster access when IDs are bounded. Both implementations compute each bill in O(k) time.

How to solve Apply Discount Every n Orders in O(n)?

Maintain a price lookup structure such as a hash map or array and keep a running order counter. For each bill request, iterate through the product list once, accumulate the total cost, and apply the discount when the order number is divisible by n. The computation is linear in the number of ordered items, giving O(k) time per order.

What is the best approach for Apply Discount Every n Orders?

The most practical approach uses a hash map to store product ID to price mappings and an internal counter to track how many customers have been served. Each call to getBill iterates through the ordered products, multiplies price by quantity, and applies the discount when orderCount % n == 0. This keeps each order calculation O(k), where k is the number of items in the order.

Is Apply Discount Every n Orders asked at Google/Amazon/Meta?

This problem belongs to the design category commonly seen in interviews at companies like Amazon and Google. It tests the ability to design a class with persistent state, perform efficient lookups, and handle repeated method calls with conditional logic.

What data structure is used in Apply Discount Every n Orders?

The core data structure is a hash table or array used to map product IDs to their prices. A simple integer counter tracks how many customers have been processed so far so the system can apply the discount every n-th order.

What is the time complexity of Apply Discount Every n Orders?

The time complexity per getBill call is O(k), where k is the number of products in the current order. Each product requires a constant-time lookup for its price and a multiplication with its quantity. Initialization takes O(P) to store the product-price mapping.

Ready to solve this problem?

Practice Apply Discount Every n Orders with our built-in code editor and test cases.

Practice on FleetCode

Apply Discount to Prices

Problem Info

DifficultyMedium

Acceptance65.5%

Approaches3

Reading time12 min

Asked at

Apply Discount Every n Orders - Solution & Explanation

Problem Statement

Approach Overview

Approach 1: Hashmap for Product Prices

Code

Complexity

Approach 2: Index Mapping with Arrays

Code

Complexity

Approach 3: Hash Table + Simulation

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Ready to solve this problem?

Problem Info

Table of Contents

Apply Discount Every n Orders - Solution & Explanation

Problem Statement

Approach Overview

Approach 1: Hashmap for Product Prices

Code

Complexity

Approach 2: Index Mapping with Arrays

Code

Complexity

Approach 3: Hash Table + Simulation

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Ready to solve this problem?

Problem Info

Table of Contents

Problem Statement

Approach Overview

Approach 1: Hashmap for Product Prices

Code

Complexity

Approach 2: Index Mapping with Arrays

Code

Complexity

Approach 3: Hash Table + Simulation

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents

Problem Statement

Approach Overview

Approach 1: Hashmap for Product Prices

Code

Complexity

Approach 2: Index Mapping with Arrays

Code

Complexity

Approach 3: Hash Table + Simulation

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents