Apply Discount Every n Orders - Practice Coding Problems

Apply Discount Every n Orders - 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⁻⁵ of the actual value will be accepted.

Input & Output

Example 1 — Basic Cashier Operations

$ Input: [["Cashier",[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]]], ["getBill",[[1,2],[1,2]]], ["getBill",[[3,7],[10,10]]], ["getBill",[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]]]]

› Output: [null,500.0,4000.0,800.0]

💡 Note: Cashier initialized with n=3, discount=50%. First customer: 1×100 + 2×200 = 500. Second customer: 10×300 + 10×100 = 4000. Third customer gets 50% discount: (1×100 + 1×200 + 1×300 + 1×400 + 1×300 + 1×200 + 1×100) × 0.5 = 800.

Example 2 — Every 2nd Customer Discount

$ Input: [["Cashier",[2,10,[1,2],[5,10]]], ["getBill",[[1],[2]]], ["getBill",[[2],[1]]]]

› Output: [null,10.0,9.0]

💡 Note: Every 2nd customer gets 10% discount. First customer: 2×5 = 10 (no discount). Second customer: 1×10 = 10, with 10% discount = 9.0.

Example 3 — Single Product Purchase

$ Input: [["Cashier",[1,20,[1],[15]]], ["getBill",[[1],[3]]]]

› Output: [null,36.0]

💡 Note: Every customer gets 20% discount (n=1). Customer buys 3 units of product 1: 3×15 = 45, with 20% discount = 45×0.8 = 36.0.

Constraints

1 ≤ n ≤ 10⁴
0 ≤ discount ≤ 100
1 ≤ products.length = prices.length ≤ 200
1 ≤ products[i] ≤ 200
1 ≤ prices[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Initialize

Store product catalog and discount rules

Process Bills

Calculate subtotal for each customer

Apply Discount

Give discount to every nth customer

Key Takeaway

🎯 Key Insight: Hash map eliminates repeated product searches, making each bill calculation efficient

Asked in

a Amazon 35 G Google 28 M Microsoft 22

The key insight is to use a hash map for O(1) product price lookups and track customer count for discount application. Best approach uses hash map for efficient price retrieval. Time: O(p + b), Space: O(p)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Linear Search	O(p × b)	O(p)	Search products array linearly for each item in the bill
Hash Map for Product Lookup	O(p + b)	O(p)	Use hash map to store product prices for O(1) lookup

Brute Force Linear Search — Algorithm Steps

Store products and prices in arrays
For each bill item, search products array linearly
Calculate subtotal and apply discount if nth customer

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Store products and prices arrays

For each bill item, search products array linearly

Calculate

Apply discount if nth customer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int n;
    int discount;
    int* products;
    int* prices;
    int productCount;
    int customerCount;
} Cashier;

Cashier* createCashier(int n, int discount, int* products, int* prices, int productCount) {
    Cashier* obj = (Cashier*)malloc(sizeof(Cashier));
    obj->n = n;
    obj->discount = discount;
    obj->products = (int*)malloc(productCount * sizeof(int));
    obj->prices = (int*)malloc(productCount * sizeof(int));
    obj->productCount = productCount;
    obj->customerCount = 0;
    
    for (int i = 0; i < productCount; i++) {
        obj->products[i] = products[i];
        obj->prices[i] = prices[i];
    }
    
    return obj;
}

double getBill(Cashier* obj, int* product, int* amount, int billSize) {
    obj->customerCount++;
    double subtotal = 0.0;
    
    for (int i = 0; i < billSize; i++) {
        // Find price for current product
        for (int j = 0; j < obj->productCount; j++) {
            if (obj->products[j] == product[i]) {
                subtotal += amount[i] * obj->prices[j];
                break;
            }
        }
    }
    
    // Apply discount if nth customer
    if (obj->customerCount % obj->n == 0) {
        subtotal = subtotal * (100 - obj->discount) / 100.0;
    }
    
    return subtotal;
}

int main() {
    printf("[null,10.0,20.0]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(p × b)

For each of b bill items, search through p products linearly

✓ Linear Growth

Space Complexity

O(p)

Store products and prices arrays

✓ Linear Space

25.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler