Eat Favourite Pizza On Given Day

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
12 upvotes
Asked in company
Amazon

Problem statement

Ninja is a Pizza lover. He can eat as much pizza as he wants. Given an array, ‘arr’ containing positive integers, where ‘arr[i]’ denotes the number of pizzas of the ‘i’th' type available in the shop. His friend ‘Emma’ gave him some challenges and asked if it is possible to complete the challenges or not by following the given rules?

The Rules are : 
1. Ninja starts eating Pizzas on day 0.

2.Ninja must eat at least one Pizza per day as he loves Pizza until he has eaten all the Pizzas.

3.If Ninja has eaten all the pizzas of 'i' - 1 type, then only he can eat a pizza of the ‘i’ type.

The challenges are given in the form of a matrix ‘mat’ in which the number of rows is equal to the number of challenges Emma offers and the number of columns is equal to 3. For any challenge 'i', the three integers ‘currentType’, ‘currentDay’, ‘maxConsumption’, denotes that Ninja has to eat the pizza of type ‘currentType’ on day ‘currentDay’ without eating more than ‘maxConsumption’ number of pizzas on any day respectively. Note that all the challenges are independent.

For Example : 
If there are two challenges [0, 1, 1] and [3, 3, 2]. For challenge 1, Ninja has to eat at least one pizza of type 0 on day 1 while eating at most 1 pizza per day. Similarly, for challenge 2, Ninja has to eat at least one pizza of type 3 on day 3 while eating at most 2 pizzas per day.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’, which denotes the number of elements in the array ‘arr’ and the number of challenges Emma gave to Ninja.

The second line of each test case contains 'N' space-separated integers denoting the elements of the array ‘arr’.

The next ‘M’ lines contain 3 space-separated integers ‘currentType’, ‘currentDay’, ‘maxConsumption’ denoting that Ninja has to eat the pizza of type currentType on day currentDay without eating more than maxConsumption number of pizzas on any day respectively.
Output Format : 
For each test case, print the answer for each challenge separated by spaces(1 denoting Ninja can complete the challenge and 0 if he can not complete the challenge).

Print the output of each test case in a separate line.
Note : 
You are not required to print the expected output, it has already been taken care of. Just implement the function and return the answer for each challenge in an array.
Constraints : 
1<= T <= 100
1 <= N <= 10^4
1 <= arr[i] <= 10^5
1 <= mat.length = 10^4
mat[i].length = 3
0 <= type < arr.length
0 <= day < 10^5
1 <= maxConsumption < 10^5

Where 'arr[i]' denotes the element at index ‘i’ of the array 'arr', type’, ‘day’, ‘maxConsumption’ denotes that Ninja has to eat the pizza of type ‘type’ on day ‘day’ without eating more than ‘maxConsumption’ number of pizzas on any day respectively. 

Time Limit: 1 sec
Sample Input 1 :
2
6 3
6 7 8 9 5 5
0 2 5
3 2 3
3 13 50
4 2
1 2 3 4
0 2 5
3 2 10
Sample Output 1 :
1 0 1
0 1
Explanation For Sample Input 1 :
In the first test case, there are 6 different types of pizzas, and the given array is [6, 7, 8, 9, 5, 5]. There are 3 challenges:
Challenge 1: Ninja has to eat pizza of 0th type on day 2. The ninja can eat a maximum of 5 pizzas per day.
One of the ways is if he eats 2 pizzas of type 0 on day 0, 2 pizzas of type 0 on day 1, 2 pizzas of type 0 on day 2, then he can complete challenge 1. 
The other way is if he eats 3 pizzas of type 0 on day 0, 2 pizzas of type 0 on day 1, 1 pizza on day 2,  then also he can complete challenge 1. 
In this way, he can complete challenge 1. So, the answer is 1.
Challenge 2:
Ninja has to eat pizza of 3rd type on day 2. The ninja can eat a maximum of 3 pizzas per day. Before day 2, he has to eat all the pizzas of type 0 and 1, i.e., he has to eat 6 + 7 = 13 pizzas before day 2, and he can eat a maximum of 3 pizzas, and there are only 2 days. 
In this way, he can’t complete challenge 2. So, the answer is 0.
Challenge 3: Ninja has to eat pizza of 3rd type on day 13. The ninja can eat a maximum of 50 pizzas per day.
He has to complete all the pizzas of type 0, 1, and 2 before day 13, i.e., eat 6 + 7 + 8 = 21 pizzas before day 13. 
One of the ways is if he eats 2 pizzas per day from day 1 to day 9, and then eats 1 pizza per day from day 10 to day 12, then he can eat all 21 pizzas on day 12 and start eating pizza of type 3 on day 13. 
In this way, he can complete challenge 3. So, the answer is 1.

In the second test case, there are 4 different types of pizzas, and the given array is [1, 2, 3, 4]. There are 2 challenges:
Challenge 1: 
Ninja has to eat pizza of the 0th type on day 2. The ninja can eat a maximum of 5 pizzas per day.
There is only 1 pizza of type 0, which he has to eat on day 1, and after that, there is no pizza of type 0 remaining. 
In this way, he can’t complete challenge 1. So, the answer is 0.
Challenge 2:
Ninja has to eat pizza of 3rd type on day 2. The ninja can eat a maximum of 10 pizzas per day. 
One of the ways is that he can eat 1 pizza of type 0 on day 0, eat 2 pizzas of type 1 on day 1 and then eat pizza of type 3 on day 2. In this way, he can complete challenge 2. So, the answer is 1.
Sample Input 2 :
2
7 3
4 5 7 6 8 2 4 
5 5 9
1 3 1 
3 2 5 
6 3
12 14 16 18 20 22 
1 2 10 
2 3 4 
4 5 20
Sample Output 2 :
1 0 0
1 0 1
Hint

Can you find out an expression for the minimum and the maximum number of days required to eat the pizza of the given type in the challenge?

Approaches (2)
Brute Force Approach

For a given challenge, we have three integers currentType, currentDay, maxConsumption, which denotes that Ninja has to eat the pizza of type currentType on day currentDay without eating more than maxConsumption number of pizzas on any day respectively. 

 

Here are two conditions:

 

  1. For eating a pizza of the currentType type, Ninja has to eat all pizzas of the currentType-1 type where i is greater than 0. For eating pizza of the 0th type, he has to start on day 0. The maximum number of pizzas Ninja can consume before day i is equal to currentDay*maxConsumption.
  2. As there is a rule that Ninja has to consume at least one pizza per day and Ninja has to consume pizza of type currentType on day currentDay, it means there should be at least 1 pizza of type currentType remaining. Let the total number of pizzas from type 0 to type currentType be K. It means at maximum Ninja can eat K - 1 pizzas before day K to eat at least one pizza on day currentDay.

 

Now, we will count the total number of pizzas from type 0 to type currentType - 1 and store it in a variable totalPizzaBeforeDay. So, from point 1, we get that that the number of days given in the challenge should be greater than or equal to the sum of all the pizzas from type 0 to type currentType - 1 divided by maxConsumption, i.e.,

 totalPizzaBeforeDay/maxConsumption <= currentDay.

 

From point 2, we get that at least one pizza should be remaining, i.e., the sum of pizzas from type 0 to type currentType - 1 should be greater than or equal to the number of days given in the challenge, i.e., totalPizzaAtDay - 1 >= currentDay.

 

Algorithm

 

  • Initialize an array answer of size equal to the number of rows in the matrix mat.
  • Iterate from i = 0 to challengeSize - 1:
    • For a given challenge, let’s say currentType, currentDay, maxConsumption, denotes that Ninja has to eat the pizza of type currentType on day currentDay without eating more than maxConsumption number of pizzas on any day respectively.
    • Initialize a variable totalPizzaBeforeDay which stores the sum of pizzas from type 0 to tye currentType - 1.
    • Iterate from j = 0 to currentType - 1:
      • Add arr[i] to totalPizzaBeforeDay.
    • Initialize a variable totalPizzaAtDay which stores the sum of pizzas from type 0 to type currentType. We have already calculated the value of totalPizzaBeforeDay. So, equate the value totalPizzaAtDay equals to totalPizzaBeforeDay + number of pizzas of current type.
    • Initialize a variable minimumDaysRequired equals to totalPizzaBeforeDay divided by maxConsumption.
    • Initialize a variable maximumDaysRequired equals to totalPizzaAtDay - 1.
    • If currentDay is greater than or equal to minimumDaysRequired and day is smaller than or equal to maxConsumption. It means Ninja can complete the i'th challenge. So, mark answer[i] = true.
    • Otherwise, mark answer[i] = false.
Time Complexity

O(N*M), where ‘N’ is the number of elements in the array ‘arr’ and ‘M’ is the number of challenges that Emma gave to Ninja.

 

In every challenge, we calculate the number of pizzas Ninja has to eat before that day which may take O(N) time in the worst case, and there are M queries. So, the time complexity is O(N*M).

Space Complexity

O(1).

 

As we are using constant extra space. So, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Eat Favourite Pizza On Given Day
Full screen
Console