Last Updated: 9 Oct, 2021
Chocolate and Sweetness
Hard
Asked in companies
Ninja wants to try some sweets in a sweet shop. There are ‘N’ types of sweets available at that shop. Each sweet has a sweetness level and expiry date. Ninja is fond of sweets, so he sets a specific sweetness level ‘X’ and is only likely to buy the sweets having a sweetness level greater than equal to ‘X’. But Ninja also wants fresher sweets, so he only buys having expiry date strictly greater than ‘Y’. Can you help Ninja to find the number of sweets suitable for him to buy?
You are given two arrays, ‘SWEET’ and ‘EXPIRY’, both having ‘N’ values corresponding to the sweetness and expiry date of ith sweet. Ninja will ask ‘Q’ queries with ‘X’ as the minimum sweetness level and ‘Y’ as the minimum expiry date. Your task is to answer all ‘Q’ queries and tell the number of sweets satisfying the given condition for each query.
For Example
For the given if N = ‘5’, ‘SWEET’ = [1,3,6,7,2] and ‘EXPIRY = [10,7,2,6,4].
And the query is ‘X’=2 and ‘Y’ =6 ,then the number of sweets satisfying the condition is only 1 (having sweetness 3 and expiry date 7).
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two integers, ‘N’ and ‘Q’, representing the number of sweets and the number of queries.
The second line of each test case contains a ‘SWEET’ array.
The third line contains the ‘EXPIRY’ array.
The next ‘Q’ line contains two integers ‘X’ and ‘Y’, for the respective query.
Output Format:
For each test case, print ‘Q’ values corresponding to the answer for each query.
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 100000.
1 <= Q <= 100000.
1 <= SWEET[i] <=100000
1 <= EXPIRY[i] <= 100000
Time limit: 1 sec
Approaches
In this approach, for each query, we will iterate over all the sweets and check if that sweet satisfies both the condition or not. If it does, we will increment our counter.
Algorithm:
- Declare the ‘ANS’ array to store the answer for each query.
- For i in range 0 to ‘Q-1’:
- Set ‘COUNT’ as 0.
- Set ‘X’ as ‘QUERY[i][0].
- Set ‘Y’ as ‘QUERY[i][0].
- For idx in range 0 to ‘N’-1, do the following:
- If ‘SWEET’[idx] ≥ ‘X’ and ‘EXPIRY[idx]’ > ’Y’:
- Set ‘COUNT’ as ‘COUNT + 1’.
- If ‘SWEET’[idx] ≥ ‘X’ and ‘EXPIRY[idx]’ > ’Y’:
- Append ‘COUNT’ to ‘ANS’ array.
- Return ‘ANS’.
In this approach, first, we will sort the values of ‘CHOCOLATES’ and ‘QUERIES’ in descending order. After that, we will prepare a Binary Indexed Tree which stores the value in sorted order, and operations like insertion and index position is done logN time. So we will build a BIT to store the values of expiry date in the sorted order.
So we will start from the sweet with the largest sweetness level and insert the corresponding expiry date value and while answering queries, we will use the index position to calculate the number of elements in the BIT whose value is less than or equal to the queried expiry date.
Algorithm:
- Declare the ‘BIT’ class for Binary Indexed Tree.
- Declare a array ‘ARR’ of size 10^5.
- Set all values of ‘ARR’ to 0.
- Declare ‘UPDATE(‘VAL’,’DIFF’)’:
- Set ‘J’ as ‘VAL’ +1.
- While ‘J’ is less than 10^5:
- Set ‘ARR[J]’ as ARR[J] + ‘DIFF’.
- Set ‘J’ as ‘J’ + (J & -J).
- Declare ‘GET_INDEX(‘VAL’)’:
- Set ‘ANS’ as 0.
- Set ‘J’ as ‘VAL’ +1.
- While ‘J’ is greater than 0:
- Set ‘ANS’ as ‘ANS’ + ‘ARR[J]’.
- Set ‘J’ as ‘J’ - (J & -J).
- Return ‘ANS’
- Declare an array of pairs ‘CHOCOLATES’.
- For i in range 0 to ‘N’-1:
- Append {‘SWEET’[i] , ‘EXPIRY’[i]} into ‘CHOCOLATES’ array.
- Declare an array ‘QUERIES’ to store the queries with their indices.
- For i in range 0 to ‘Q’-1:
- Append {i , ‘QUERIES[i][0] , QUERIES[i][1]}.
- Sort ‘CHOCOLATES’ array in descending order of sweetness level.
- Also, sort ‘QUERIES’ array in descending order of the sweetness level.
- Set i as 0 and j as 0.
- Declare a Binary Indexed Tree as ‘EXPIRY_BIT’
- Declare an array ‘ANS’ of size Q to store the answer to all queries.
- While i is less than ‘N’ and j is less than ‘Q’, do the following:
- If the sweetness of ‘CHOCOLATE[i]’ >= sweetness of ‘QUERY[j]’:
- Insert expiry of ‘CHOCOLATE[i] in the ‘EXPIRY_BIT’.
- Set ‘IDX’ as GET_INDEX(expiry date of ‘QUERIES[j]’).
- Set ‘ANS[Index of ‘QUERIES[j]’]’ as i+1 - ‘IDX’ .
- Set i as i+1.(Try the next sweet.)
- Else:
- Set j as j+1. (Try the next query).
- If the sweetness of ‘CHOCOLATE[i]’ >= sweetness of ‘QUERY[j]’:
- If all sweets are processed and some queries are left.
- While j is less than ‘Q’:
- Set ‘IDX’ as GET_INDEX(expiry date of ‘QUERIES[j]’).
- Set ‘ANS[Index of ‘QUERIES[j]’]’ as N - ‘IDX’ .
- Set j as j+1.
- Answer for all queries are computed.
- Return ‘ANS’ array
Similar problems