Black Friday

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
OYO

Problem statement

It’s black friday and the supermarket near Ninja’s house is offering a special discount to every Nth customer that generates a bill. You are initially given 2 arrays, “PRODUCTS” and “PRICES” where “PRODUCTS[i]” represents the ID of the ith product and “PRICES[i]” represents the price of the ith product per unit. You are also given an integer “DISCOUNT” which represents the discount percentage for every nth customer (i.e. the effective amount to be paid would be ‘(100 - discount) / (100 * amount’).

For each customer that visits the store, you are given 2 arrays, “PRODUCTID” and “QUANTITY” where “PRODUCTID[i]” represents the ID of the ith product and “QUANTITY[i]” represents the quantity of the ith product purchased by the customer.

Your task is to implement the following 2 functions:

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.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
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”.
Output Format : 
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.
Note: 
Print the result till 5 decimal places
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given functions.
Constraints: 
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
Sample Input 1 :
1
2 90 8
5 4 2 8 3 6 7 1 
40 10 50 20 90 90 30 20 
2
5
1 3 4 5 8 
8 5 4 1 6 
3
3 4 5 
6 3 7
Sample Output 1:
810.00000
85.00000

Explanation for Sample 1:

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
Sample Input 2 :
2
1 72 3
2 3 1 
19 53 11 
1
3
1 2 3 
3 1 3 
3 43 2
2 1 
101 20
2 
2
1 2 
1 2 
2
1 2 
1 1
Sample Output 2 :
59.08000
222.00000
121.00000
Hint

Can we keep a count of the number of customers to find which customers get the discount?

Approaches (1)
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).

Code Solution
(100% EXP penalty)
Black Friday
Full screen
Console