Black Friday

1. blackFriday(int N, int discount, int[] products, int[] prices) where every Nth customer receives a discount, “discount” is the discount percentage, “products” contains the product IDs, and “prices” contains the prices of products. 2. generateBill(int[] productID, int[] quantity) where “productID” contains the product IDs and “quantity” contains the quantities of products purchased by the customer.

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows. The first line contains three space-separated integers ‘N’, “discount” and ‘S’ denoting the customer’s getting a discount, discount percentage and number of products. The next line contains ‘S’ space-separated integers denoting the array “products”. The next line contains ‘S’ space-separated integers denoting the array “prices”. The next line of each test case contains an integer ‘K’ denoting the number of queries. For the next K queries: The first line contains an integer ‘S’ denoting the number of distinct products purchased. The next line contains ‘S’ space-separated integers denoting the array “productID”. The next line contains ‘S’ space-separated integers denoting the array “quantity”.

For each test case, return a list containing the bill amount for each customer after discount(if applicable) in the order they generated the bill. Output for each test case will be printed in a new line.

1 <= T <= 100 1 <= K <= 1000 1 <= S <= 100 1 <= productID[i], products[i], quantity[i], prices[i] <= 1000 Where ‘T’ denotes the number of test cases, ‘K’ denotes the number of queries and ‘S’ denotes the number of products Time Limit: 1sec

Customer number1's bill = 8*20 + 5*90 + 4*10 + 1*40 + 6*20 = 810.00000 Customer number2's bill = 6*90 + 3*10 + 7*40 = 850.00000 But since 2 is divisible by 2, after discount price is = 850.00000*10/100 = 85.00000

Counting Number of Previous Customers

We can simply start by creating a hashmap that stores each product ID and corresponding price. For each customer, calculating the bill amount is simple, just multiply the quantity by the price of each product they purchased.

We also keep a count of previous customers and increase it as soon as generateBill is called. If this count is divisible by ‘N’, we simply apply the discount and return the bill amount.

Algorithm:

Create a hashmap “productPrice” which maps each product ID to its price.
Store the number of previous customers in a variable “customerCount” and initialize it with 0.
Each time “generateBill” is called, increase “customerCount”.
Calculate the bill by iterating “productID” and “quantity” array using the expression: billAmount = Σ(productID[i] * quantity[i]) for i ranging from 0 to length of productID array.
If “customerCount” is divisible by ‘N’, reduce “billAmount” by “discount” percent.
Return “billAmount”.

Time Complexity

O(K * S), where ‘K’ denotes the number of queries and ‘S’ denotes the number of distinct products.

Note that in each query, we iterate through each product at most once in each query

Therefore time complexity for each of the ‘K’ queries is at most O(S), the total time complexity is O(K * S).

Space Complexity

O(S), where ‘S’ denotes the number of distinct products.

Since we are using a hashmap of size ‘S’ to store our prices, the overall space complexity is O(S).

Problem statement

Sample Input 1 :

Sample Output 1:

Explanation for Sample 1:

Sample Input 2 :

Sample Output 2 :