Jasprit and Hits

Easy
0/40
Average time to solve is 10m
profile
Contributed by
15 upvotes

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5 3
1 4 5 8 3
1 0
2 2 5
2 6 6
1 2
0
2 1 1
1 5
Sample Output 1 :
5 0
0
Explanation Of Sample Input 1 :
For the first test case,
After the first query, the array ‘ARR’ = [1, 4, 5, 8, 3, 0].
In the second query, the sum = 4+5+8+3 = 20 and number of elements is 4, hence the average = 20/4 = 5.
In the third query, the sum = 0 and number of elements is 1, hence the average = 0/1 = 0.

Hence, the output will be: 5 0

For the second test case,
In the first query, the sum = 0 and number of elements is 1, hence the average = 0/1 = 0.
After the second query, the array ‘ARR’ = [0, 5].

Hence, the output will be: 0
Sample Input 2 :
2
1 4
5
1 2
2 1 2
1 3
2 2 3
5 1
1 2 3 4 5
2 1 5
Sample Output 2 :
3 2
3
Hint

Can we try to add the elements in a dynamic way and then find the average?.

Approaches (2)
Brute Force

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’.
  • Return ‘ANS’.
Time Complexity

O(N*Q), Where ‘N’ and ‘Q’ are input integers.

In the worst case, all the queries can be of type 2, with ‘L=1’ and ‘R=N’ which will have O(N) time complexity for each query to find the sum, hence the time complexity will be O(N*Q)

Space Complexity

O(N + Q), Where ‘N’ and ‘Q’ are input integers.


As we create the copy of the array ‘ARR’ of length ‘N’ and we also created an array ‘ANS’ which will store the answer for all queries of type 2, which in the worst case can be ‘Q’, hence the space complexity will be O(N + Q).

Code Solution
(100% EXP penalty)
Jasprit and Hits
Full screen
Console