Last Updated: 26 Apr, 2021

Eat Favourite Pizza On Given Day

Moderate

Asked in company

Solve now

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.

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

Solve now

Approaches

01 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:

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.
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.

Solve now

02 Approach

From the above approach, we are taking at most O(N) time in each challenge.

Can we improve it?

We will make a prefix array in which index i will store the sum of all the pizzas from type 0 to type currentType. For any challenge, we won’t have to iterate and find the sum of pizzas from type 0 to type currentType, it is already present in the array prefixSum.

The rest of the steps are the same as the previous approach.

Algorithm

Initialize an array answer of size equal to the number of rows in the matrix mat.
Initialize an array prefixSum of size N in which index i will store the sum of all the pizzas from type 0 to type currentType.
Initialize the first value of prefixSum equals to the first value of the array arr.
Iterate from i = 1 to N - 1;
- Equate the value of prefixSum[i] equals to arr[i] + prefixSum[i-1].
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 type currentType - 1.
- Set totalPizzaBeforeDay as prefixSum[type - 1].
- Initialize a variable totalPizzaAtDay which stores the sum of pizzas from type 0 to type currentType. As we have already calculated the value of totalPizzaBeforeDay. So, totalPizzaAtDay will be equal tototalPizzaBeforeDay + the number of pizzas of the current type.
- Initialize a variable minimumDaysRequired as totalPizzaBeforeDay divided by maxConsumption.
- Initialize a variable maximumDaysRequired as totalPizzaAtDay - 1.
- If the current day is greater than or equal to minimumDaysRequired and the current day is smaller than or equal to maximumDaysRequired. It means Ninja can successfully complete the i'th challenge. So, mark answer[i] as true.
- Otherwise, mark answer[i] as false.

Solve now