Last Updated: 14 Jul, 2022
Jasprit and Hits
Easy
Jasprit loves playing cricket. He wants to be a part of the Indian cricket team and become the best pacer for India. So he started practicing every day and took guidance from his coach. Every day to measure how he is improving, he maintained the count of times he hits the stumps in a day.
‘N’ days have been passed and its track is denoted by the array ‘ARR’, and to track his improvement, his coach will also ask him the average count of hits of stumps per day for a particular range of days (i.e. ‘L’ to ‘R’) to him. Meanwhile, he will also add the count of time he hits the stumps in the ongoing days.
Jasprit is not very good at maths, So being his friend he asked you to help him to add the count of times he hit the stumps in the day as well as give the average count of hits of stumps per day for a particular range of days asked by his coach.
There will be a ‘Q’ number of such queries where each query will be either one of the following types:
1) Add the stumps hit by Jasprit i.e. ‘X’ to the array ‘ARR’, denoted by query number ‘1’.
2) Give the average of hits of stumps per day for days ranging from ‘[L, R]’ asked by his coach denoted by query number ‘2’.
Can you help him with this problem?.
NOTE: The average here means the sum of all elements in the selected range divided by the number of elements rounded down, i.e. let's suppose ‘sum’ = 10 and ‘number of elements’ = 4, then the average will be = 10/4 = 2.5, which when rounded down gives 2.
The array ‘ARR’ is 0-based indexing and queries of type 2 are represented in 1-based indexing.
The answer to the query of type 2 will be rounded down to an integer.
EXAMPLE :
Input: ‘N’ = 2, ‘Q’ = 2, ‘ARR’ = [7, 5], ‘QUERIES’ = [[1, 8], [2, 1, 3]].
Output: 6
In this case, the array ‘ARR’ after the first query will be ‘ARR’ = [7, 5, 8].
In the second query, the average will be = the sum of hits from day 1 to day 3 divided by 3
i.e. (7+5+8)/3 = 20/3 = 6.6666… when rounded gives 6. Hence the output will be 6.
Input Format :
The first line will contain the integer ‘T’, the number of test cases.
The first line of each test case contains two integers, ‘N’ and ‘Q’ separated by spaces.
Followed by a line containing space-separated ‘N’ non-negative integers, denoting the elements of the array ‘ARR’.
Followed by ‘Q’ lines, each of the following types:
(1) If its query ‘1’, it will consist of two space-separated numbers, ‘1’ and ‘X’, where ‘X’ denotes the number to be added at the end of the existing array ‘ARR’.
(2) If its query ‘2’, it will consist of three space-separated numbers, ‘2’ and ‘L’ and ‘R’.
Output format :
For each test case, print the average count of hits of stumps per day for every query of type ‘2’.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
1 <= ‘Q’ <= 10^5
0 <= ‘ARR[i]’ <= 10^4
0 <= ‘X’ <= 10^4
1 <= ‘L’ <= ‘R' <= Total number of elements in the array ‘ARR’, before this operation.
It is guaranteed that sum of ‘N’ over all test cases is <= 10^5
It is guaranteed that sum of ‘N’ over all test cases is <= 10^5
It is guaranteed that there will be atleast one query of type ‘2’.
Time Limit: 1 sec
Approaches
The idea for this approach is to use a list data structure (here list is the dynamic array) to add the elements into an existing array and then iterate on the array for the given range and find out its average.
We can first create a copy of the given array ‘ARR’ into our list and then perform the queries in the given order.
Algorithm:
// The function will return the answers for all queries of type ‘2’.
Int[] getAverage(N, Q, ARR, QUERIES)
- Create a list ‘LIST’.
- Create a list ‘ANS’.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Insert ‘ARR[i]’ to the end of the list ‘LIST’.
- Run a for loop from ‘0’ to ‘Q-1’ with a variable named ‘i’.
- If ‘QUERIES[i][0] == 1’
- Insert ‘QUERIES[i][1]’ to the end of the list ‘LIST’.
- Else
- Initialize the variable ‘sum’ with the value ‘0’.
- Initialize the variable ‘L’ with the value ‘QUERIES[i][1] - 1’.
- Initialize the variable ‘R’ with the value ‘QUERIES[i][2] - 1’.
- Initialize the variable ‘length’ with the value ‘R - L + 1’.
- Run a for loop from ‘L’ to ‘R’ with a variable named ‘j’.
- Add ‘LIST[j]’ to ‘sum’.
- Insert ‘sum/length’ to the end of the list ‘ANS’.
- If ‘QUERIES[i][0] == 1’
- Return ‘ANS’.
The idea for this approach is to use the prefix sum technique, using this we can find the sum for any range in O( 1 ) time. For that, we will need to pre-process the sum from ‘0’ to ‘i’ for ‘0’ <= ‘i’ <= ‘N-1’ and store it in an array. Let’s call it the ‘prefixSum’ array. We will use a dynamic array which we have called a list here.
Whenever there is a query of type 1, we can find the sum up to the last element of array ‘ARR’, from the value stored at the last element of the array ‘prefixSum’. We will push the sum of the new element and the sum of all elements up to now and insert it at the end of the array ‘prefixSum’.
For query of type 2, we can find the sum of range ‘L’ to ‘R’ using the ‘prefixSum’ array. This can be found by adding the sum of all elements up to index ‘R’ and removing the sum of all elements up to index ‘L-1’. In this way, we get the sum of all elements in the range ‘[L, R]’ and then divide it by ‘R - L + 1’ to get the average.
One of the edge cases for this approach is when ‘L = 1’, in this case, we don’t have to remove the sum of any elements before ‘1’.
Algorithm:
// The function will return the answers for all queries of type ‘2’.
Int[] getAverage(N, Q, ARR, QUERIES)
- Create a list ‘prefixSum’ with an initial length of ‘N’.
- Create a list ‘ANS’.
- Initialize the variable ‘sum’ with the value of ‘0’.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Add ‘ARR[i]’ to ‘sum’.
- Assign ‘prefixSum[i]’ the value of ‘sum’.
- Run a for loop from ‘0’ to ‘Q-1’ with a variable named ‘i’.
- If ‘QUERIES[i][0] == 1’
- Initialize the variable named ‘newSum’ with the value of the last element of the list ‘prefixSum’.
- Add ‘QUERIES[i][1]’ to ‘newSum’.
- Insert ‘newSum’ at the end of the list ‘prefixSum’.
- Else
- Initialize the variable ‘L’ with the value ‘QUERIES[i][1] - 1’.
- Initialize the variable ‘R’ with the value ‘QUERIES[i][2] - 1’.
- Initialize the variable ‘length’ with the value ‘R - L + 1’.
- Initialize the variable named ‘currSum’ with the value of ‘prefixSum[R]’.
- If ‘L != 0’
- Subtract ‘prefixSum[L-1]’ from ‘currSum’.
- Insert ‘currSum/length’ to the end of the list ‘ANS’.
- If ‘QUERIES[i][0] == 1’
- Return ‘ANS’.