# Apply Discount Every n Orders
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/apply-discount-every-n-orders)
Canonical: https://scaleengineer.com/dsa/problems/apply-discount-every-n-orders
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array, Hash Table
---
## Problem
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 `ith` 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 `jth` 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 jth product)`.

The supermarket decided to have a sale. Every `nth` 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. 1st customer, no discount.
                                                     // bill = 1 * 100 + 2 * 200 = 500.
cashier.getBill([3,7],[10,10]);                      // return 4000.0. 2nd 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. 3rd customer, 50% discount.
                                                     // Original bill = 1600
                                                     // Actual bill = 1600 * ((100 - 50) / 100) = 800.
cashier.getBill([4],[10]);                           // return 4000.0. 4th customer, no discount.
cashier.getBill([7,3],[10,10]);                      // return 4000.0. 5th customer, no discount.
cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); // return 7350.0. 6th 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.  7th customer, no discount.

**Constraints:**

* `1 <= n <= 104`
* `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.

# Approaches
## Brute-Force with Linear Search
This approach directly implements the logic described in the problem without any optimization. In the constructor, we simply store the initial parameters (`n`, `discount`, `products`, `prices`) and initialize a customer counter. For each `getBill` call, we calculate the subtotal by iterating through the customer's items. For each item, we perform a linear search through the supermarket's `products` array to find its corresponding price. After calculating the total bill, we check if a discount should be applied based on the customer count.
**Time:** O(M * P) for each `getBill` call, where `M` is the number of products in the customer's bill and `P` is the total number of products available in the supermarket. The constructor is `O(1)`. · **Space:** O(P) to store the product and price lists, where P is the number of unique products in the supermarket.
**Pros:** Very simple to understand and implement.; No preprocessing required in the constructor, leading to a very fast initialization.
**Cons:** Inefficient for `getBill` calls. The repeated linear search for prices can be very slow if the number of products in the supermarket is large.
### Explanation
We maintain a customer counter, `customerCount`, which is incremented for every call to `getBill`. The `getBill` method iterates through each product in the customer's cart. Inside this loop, another loop iterates through the `products` array (from the constructor) to find a match for the current product ID. Once the product ID is found at index `i`, its price `prices[i]` is retrieved. The cost for this item (`price * amount`) is added to the `subtotal`. After iterating through all items in the cart, we check if `customerCount` is a multiple of `n`. If it is, the discount is applied to the `subtotal`. The final bill is then returned.

```java
class Cashier {
    private int n;
    private int discount;
    private int[] products;
    private int[] prices;
    private int customerCount;

    public Cashier(int n, int discount, int[] products, int[] prices) {
        this.n = n;
        this.discount = discount;
        this.products = products;
        this.prices = prices;
        this.customerCount = 0;
    }

    public double getBill(int[] product, int[] amount) {
        this.customerCount++;
        double subtotal = 0.0;

        for (int i = 0; i < product.length; i++) {
            int currentProductId = product[i];
            int currentAmount = amount[i];
            int price = 0;
            // Linear search for the price
            for (int j = 0; j < this.products.length; j++) {
                if (this.products[j] == currentProductId) {
                    price = this.prices[j];
                    break;
                }
            }
            subtotal += price * currentAmount;
        }

        if (this.customerCount % this.n == 0) {
            subtotal = subtotal - (subtotal * this.discount) / 100.0;
        }

        return subtotal;
    }
}
```
### Algorithm
*   Initialize `customerCount = 0` in the constructor. Store `n`, `discount`, `products`, and `prices`.
*   In `getBill(product, amount)`:
    *   Increment `customerCount`.
    *   Initialize `subtotal = 0.0`.
    *   For each item in the customer's cart:
        *   Perform a linear search on the main `products` array to find the item's price.
        *   Add `price * amount` to `subtotal`.
    *   If `customerCount` is a multiple of `n`, apply the discount to `subtotal`.
    *   Return the final bill.

## Optimized Approach using a HashMap
This approach improves the performance of `getBill` by pre-processing the product and price data. In the constructor, we create a `HashMap` to store product IDs as keys and their corresponding prices as values. This allows for near-constant time `O(1)` price lookups. When `getBill` is called, we can quickly retrieve the price for each item in the customer's cart from the HashMap, significantly speeding up the subtotal calculation.
**Time:** The constructor takes `O(P)` time to build the HashMap, where `P` is the number of products. Each `getBill` call takes `O(M)` time, where `M` is the number of products in the customer's bill, because HashMap lookups are `O(1)` on average. This is a significant improvement over the brute-force approach, especially when `getBill` is called many times. · **Space:** O(P) to store the `priceMap`, where P is the number of unique products.
**Pros:** Highly efficient `getBill` method with `O(M)` time complexity.; Well-suited for scenarios with frequent `getBill` calls.
**Cons:** Requires extra space for the HashMap.; Incurs a one-time preprocessing cost in the constructor.
### Explanation
The key optimization is to avoid the costly linear search for prices. We use a `HashMap` for this purpose. In the `Cashier` constructor, we iterate through the `products` and `prices` arrays once and populate a `HashMap`. The map will have `productID` -> `price` mappings. The `getBill` method remains structurally similar. It increments the customer counter and calculates the subtotal. However, to find the price of an item, instead of a linear search, it performs a quick lookup in the `HashMap`. This reduces the time to find a price from `O(P)` to `O(1)` on average. The rest of the logic for applying the discount remains the same.

```java
import java.util.HashMap;
import java.util.Map;

class Cashier {
    private int n;
    private int discount;
    private Map<Integer, Integer> priceMap;
    private int customerCount;

    public Cashier(int n, int discount, int[] products, int[] prices) {
        this.n = n;
        this.discount = discount;
        this.priceMap = new HashMap<>();
        for (int i = 0; i < products.length; i++) {
            this.priceMap.put(products[i], prices[i]);
        }
        this.customerCount = 0;
    }

    public double getBill(int[] product, int[] amount) {
        this.customerCount++;
        double subtotal = 0.0;

        for (int i = 0; i < product.length; i++) {
            int currentProductId = product[i];
            int currentAmount = amount[i];
            int price = this.priceMap.get(currentProductId);
            subtotal += price * currentAmount;
        }

        if (this.customerCount % this.n == 0) {
            subtotal = subtotal - (subtotal * this.discount) / 100.0;
        }

        return subtotal;
    }
}
```
### Algorithm
*   In the constructor, initialize `customerCount = 0`, `n`, and `discount`.
*   Create a `HashMap<Integer, Integer>` called `priceMap`.
*   Iterate through the `products` and `prices` arrays and populate `priceMap` with `(products[i], prices[i])` pairs.
*   In `getBill(product, amount)`:
    *   Increment `customerCount`.
    *   Initialize `subtotal = 0.0`.
    *   For each item in the customer's cart:
        *   Get the price from `priceMap` in `O(1)` average time.
        *   Add `price * amount` to `subtotal`.
    *   If `customerCount` is a multiple of `n`, apply the discount.
    *   Return the final bill.

# Solutions
### Java

```java
class Cashier { private int i ; private int n ; private int discount ; private Map < Integer , Integer > d = new HashMap <>(); public Cashier ( int n , int discount , int [] products , int [] prices ) { this . n = n ; this . discount = discount ; for ( int j = 0 ; j < products . length ; ++ j ) { d . put ( products [ j ], prices [ j ]); } } public double getBill ( int [] product , int [] amount ) { int dis = (++ i ) % n == 0 ? discount : 0 ; double ans = 0 ; for ( int j = 0 ; j < product . length ; ++ j ) { int p = product [ j ], a = amount [ j ]; int x = d . get ( p ) * a ; ans += x - ( dis * x ) / 100.0 ; } return ans ; } } /** * Your Cashier object will be instantiated and called as such: * Cashier obj = new Cashier(n, discount, products, prices); * double param_1 = obj.getBill(product,amount); */
```

### CPP

```cpp
class Cashier { public: Cashier ( int n , int discount , vector < int >& products , vector < int >& prices ) { this -> n = n ; this -> discount = discount ; for ( int j = 0 ; j < products . size (); ++ j ) { d [ products [ j ]] = prices [ j ]; } } double getBill ( vector < int > product , vector < int > amount ) { int dis = ( ++ i ) % n == 0 ? discount : 0 ; double ans = 0 ; for ( int j = 0 ; j < product . size (); ++ j ) { int x = d [ product [ j ]] * amount [ j ]; ans += x - ( dis * x ) / 100.0 ; } return ans ; } private: int i = 0 ; int n ; int discount ; unordered_map < int , int > d ; }; /** * Your Cashier object will be instantiated and called as such: * Cashier* obj = new Cashier(n, discount, products, prices); * double param_1 = obj->getBill(product,amount); */
```

### Python

```python
class Cashier : def __init__ ( self , n : int , discount : int , products : List [ int ], prices : List [ int ]): self . i = 0 self . n = n self . discount = discount self . d = { product : price for product , price in zip ( products , prices )} def getBill ( self , product : List [ int ], amount : List [ int ]) -> float : self . i += 1 discount = self . discount if self . i % self . n == 0 else 0 ans = 0 for p , a in zip ( product , amount ): x = self . d [ p ] * a ans += x - ( discount * x ) / 100 return ans # Your Cashier object will be instantiated and called as such: # obj = Cashier(n, discount, products, prices) # param_1 = obj.getBill(product,amount)
```