Last Updated: 31 Jul, 2022
Ravi and Coins
Moderate
Asked in company
Ravi is fond of collecting coins. He has ‘N’ boxes with him numbered from ‘0’ to ‘N-1’, initially, all the boxes are empty.
Now for the next ‘M’ days, Ravi adds one coin to each box from ‘[L, R]’, it is denoted by the 2d-array ‘ARR’. (The range ‘L’ to ‘R’ may or may not be the same for each of the ‘M’ days).
Now Deep was very good at maths and being a friend of Ravi he challenged him to answer ‘Q’ questions, denoted by the array ‘QUERIES’ after the ‘M’ days have passed.
Each question will have a number ‘X’ and Ravi has to find the number of boxes having at least ‘X’ coins in it. (i.e. number of boxes having more than or equal to ‘X’ coins).
Now Ravi has found the answers to the questions but is not sure if they are completely correct, So he has asked you to calculate the answers to these questions. Can you help him?.
EXAMPLE :
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.
Input Format :
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’.
Output format :
For each test case, print ‘Q’ space separated integers denoting the answers to the ‘Q’ questions asked by Deep.
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 <= ‘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
Approaches
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’.
- Run a for loop from ‘ARR[i][0]’ to ‘ARR[i][1]’ with a variable named ‘j’.
- 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’.
- If ‘BOXES[j] >= QUERY[i]’
- Assign ‘ANS[i]’ the value of ‘COUNT’.
- Return ‘ANS’.
The idea for this approach is to optimize the brute force idea by using a prefix sum technique to add the coins in O( 1 ) time and then preprocess the number of boxes having more than some number of coins using a suffix sum technique.
So first to add the coins in O( 1 ) time we can use a prefix sum technique, whenever we are said to add a coin in the range ‘L’ to ‘R’ we can increment the contribution for the box ‘L’ and decrement the contribution of the box ‘R+1’ by ‘1’. And then at the end, we will do a prefix sum over the whole array, in this way the contribution of +1 at ‘L’ will be cut out by the ‘-1’ at the positions ‘R+1’ and hence all the boxes from ‘L’ to ‘R’ will have a ‘1’ coin added.
And then after ‘M’ day's operations and performing prefix sum, we will create an array ‘suffSum’ of length ‘M+1’ and iterate on the ‘BOXES’ array (used to perform prefix sum) and find the frequency of boxes having ‘i’ coins, where 0 <= ‘i’ <= ‘M’. We will never have any box greater than ‘M’ coins as there are only ‘M’ days and on each day we add only ‘1’ coin to any box.
Now after finding the frequency we will perform a suffix sum on the array ‘suffSum’, to find the boxes having greater than or equal to ‘i’ number of coins, where 0 <= ‘i’ <= ‘M’. We use suffix sum because we have questions of the type: find boxes having at least ‘X’ coins.
Now when answering questions, we first check if asked ‘X’ > ‘M’ then it is impossible to have any box containing more than ‘M’ coins so we simply print ‘0’ or else we print the value of ‘suffSum[X]’.
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+1’ with the initial value of ‘0’.
- Run a for loop from ‘0’ to ‘M-1’ with a variable named ‘i’.
- Increment the ‘BOXES[ARR[i][0]]’ by ‘1’.
- Decrement the ‘BOXES[ARR[i][1] + 1]’ by ‘1’.
- Create an array named ‘suffSum’ of length ‘M+1’ with the initial value of ‘0’.
- Increment ‘suffSum[BOXES[0]]’ by ‘1’.
- Run a for loop from ‘1’ to ‘N-1’ with a variable named ‘i’.
- Add ‘BOXES[i-1]’ to ‘BOXES[i]’.
- Increment ‘suffSum[BOXES[i]]’ by ‘1’.
- Run a for loop in reverse manner ‘M-1’ to ‘0’ with a variable named ‘i’.
- Add ‘suffSum[i+1]’ to ‘suffSum[i]’.
- 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’.
- If ‘QUERIES[i] <= M’
- Assign ‘COUNT’ the value of ‘suffSum[QUERIES[i]]’.
- Assign ‘ANS[i]’ the value of ‘COUNT’.
- Return ‘ANS’.