Ravi and Coins

Input: ‘N’ = 3, ‘M' = 2, ‘Q’ = 1, ‘ARR’ = [[0, 1], [0, 2]], ‘QUERIES’ = [2] Output: 2 In this case, After Day 1 number of coins in the boxes will be: [1, 1, 0] After Day 2 number of coins in the boxes will be: [2, 2, 1] Hence the boxes having at least ‘2’ coins are Box 0 and Box 1.

The first line will contain the integer ‘T’, the number of test cases. Each test case consists of two lines. The first line of input contains three integers, ‘N’, ‘M’, and ‘Q’ separated by spaces. Followed by ‘M’ lines, each line contains two integers, ‘L’ and ‘R’. Followed by ‘Q’ lines, each line contains one integer, ‘X’.

1 <= ‘T’ <= 10 1 <= ‘N’ <= 10^5 1 <= ‘M’ <= 10^5 1 <= ‘Q’ <= 10^5 0 <= ‘L’ <= ‘R’ <= ‘N-1’ 0 <= ‘X’ <= 10^5 It is guaranteed that sum of ‘N’ over all test cases is <= 10^5 It is guaranteed that sum of ‘M’ over all test cases is <= 10^5 It is guaranteed that sum of ‘Q’ over all test cases is <= 10^5 Time Limit: 1 sec

For the first test case, After Day 1 number of coins in the boxes will be: [0, 1, 1, 1, 1] Hence the boxes having at least ‘1’ coin are Box 1, 2, 3, and 4. Hence, the output will be: 4 For the second test case, After Day 1 number of coins in the boxes will be: [1, 1, 1, 1, 0, 0, 0] After Day 2 number of coins in the boxes will be: [1, 1, 2, 2, 1, 1, 1] After Day 3 number of coins in the boxes will be: [1, 1, 2, 2, 2, 2, 2] All the boxes have at least a ‘1’ coin, hence the answer to the ‘1’st question is ‘7’. The boxes having at least ‘2’ coins are Box 2, 3, 4, 5, and 6. Hence, the output will be: 7 5

Brute Force

The idea for this approach is to add the coins for the range ‘L’ to ‘R’ using a loop for every day. And then to answer questions we will iterate through the ‘N’ boxes and keep the count for the boxes having >= ‘X’ coins.

To implement this we have to keep an array, let’s call it ‘BOXES’ of length ‘N’ initially filled with ‘0’. And then add ‘1’ to the indices ‘L’ to ‘R’ for every day.

Algorithm:

// The function will return the answers to the questions denoted by the array ‘QUERY’.

Int[] getAnswers(N, M, Q, ARR, QUERIES)

Create an array named ‘BOXES’ of length ‘N’ with the initial value of ‘0’.
Run a for loop from ‘0’ to ‘M-1’ with a variable named ‘i’.
- Run a for loop from ‘ARR[i][0]’ to ‘ARR[i][1]’ with a variable named ‘j’.
  - Increment ‘BOXES[j]’ by ‘1’.
Create an array ‘ANS’ of the length ‘Q’.
Run a for loop from ‘0’ to ‘Q-1’ with a variable named ‘i’.
- Initialize the variable named ‘COUNT’ with the value of ‘0’.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘j’.
  - If ‘BOXES[j] >= QUERY[i]’
    - Increment ‘COUNT’ by ‘1’.
- Assign ‘ANS[i]’ the value of ‘COUNT’.
Return ‘ANS’.

Time Complexity

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

In the above algorithm, in the worst case when every day we have to add a coin for all the boxes from ‘0’ to N-1’ i.e. ‘L’ = 1 and ‘R’ = ‘N-1’, there will be in total ‘M*N’ iterations to update the array ‘BOXES’. Also for every question of the array ‘QUERIES’ of length ‘Q’, we iterate through each element of the array ‘BOXES’ of the length ‘N’, which will have total Q*N iterations.

Hence the time complexity will be O( M * N + Q * N )

Space Complexity

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

In the above algorithm, we use an array ‘BOXES’ of length ‘N’ to keep track of the coins added while ‘M’ days and we also use an array ‘ANS’ of length ‘Q’ to return the answers to the questions denoted by the array ‘QUERIES’.

Hence the space complexity will be O( N + Q ).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation Of Sample Input 1 :

Sample Input 2 :

Sample Output 2 :