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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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 <= 10^4
  • 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.

Solution

Method 1 – Hash Map for Product Prices & Counter for Discount

Intuition

The key idea is to efficiently look up product prices using a hash map and keep track of the number of customers served. Every nth customer receives a discount, so we increment a counter with each bill and apply the discount when needed.

Approach

  1. Store product IDs and their prices in a hash map for O(1) lookup.
  2. Maintain a counter to track the number of customers.
  3. For each bill:
  • Calculate the subtotal by summing up amount[j] * price of product[j].
  • Increment the customer counter.
  • If the counter is divisible by n, apply the discount.
  • Return the final bill amount.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
   unordered_map<int, int> price;
   int n, discount, cnt = 0;
public:
   Solution(int n, int discount, vector<int>& products, vector<int>& prices) {
      this->n = n;
      this->discount = discount;
      for (int i = 0; i < products.size(); ++i)
        price[products[i]] = prices[i];
   }
   double getBill(vector<int>& product, vector<int>& amount) {
      ++cnt;
      double ans = 0;
      for (int i = 0; i < product.size(); ++i)
        ans += price[product[i]] * amount[i];
      if (cnt % n == 0)
        ans = ans * (100 - discount) / 100.0;
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
   private Map<Integer, Integer> price = new HashMap<>();
   private int n, discount, cnt = 0;
   public Solution(int n, int discount, int[] products, int[] prices) {
      this.n = n;
      this.discount = discount;
      for (int i = 0; i < products.length; i++)
        price.put(products[i], prices[i]);
   }
   public double getBill(int[] product, int[] amount) {
      cnt++;
      double ans = 0;
      for (int i = 0; i < product.length; i++)
        ans += price.get(product[i]) * amount[i];
      if (cnt % n == 0)
        ans = ans * (100 - discount) / 100.0;
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
   def __init__(self, n: int, discount: int, products: list[int], prices: list[int]):
      self.n = n
      self.discount = discount
      self.price = {pid: p for pid, p in zip(products, prices)}
      self.cnt = 0

   def getBill(self, product: list[int], amount: list[int]) -> float:
      self.cnt += 1
      ans = sum(self.price[pid] * amt for pid, amt in zip(product, amount))
      if self.cnt % self.n == 0:
        ans = ans * (100 - self.discount) / 100
      return ans

Complexity

  • ⏰ Time complexity: O(k) per getBill call, where k is the number of products in the bill.
  • 🧺 Space complexity: O(m), where m is the number of unique products.