Chocolate and Sweetness

Hard
0/120
9 upvotes
Asked in companies
ShareChatGoogle inc

Problem statement

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).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 2
1 3 6 7 2
10 7 2 6 4
2 6
3 9
3 1 
1 5 7
11 7 10
3 6
Sample Output 1:
1 0
2
Explanation of sample input 1:
For the first test case,
For the first query, the number of sweets having sweetness greater than 2 and expiry greater than 6 is only 1(Sweet number 4 ).
For the second query, there is no sweet satisfying both the condition. Hence the answer is 0.

Hence the answer is [1,0].

For the second test case:
The number of sweets satisfying both the conditions is 2. (2nd and the 3rd sweet.)
 Hence the answer is [2].
Sample Input 2:
2
5 2
2 9 4 8 7 
3 8 3 2 8 
7 9
3 3
4 3
9 2 6 4 
1 10 10 2 
1 2
7 2
2 2
Sample Output 2:
0 2
2 0 2
Hint

 Try to check each sweet for each query.

Approaches (2)
Brute Force

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

O(N*Q), where ‘N’ is the number of sweets, and ‘Q’ is the number of queries.

 

In this approach, for each query, we are checking all sweets if they satisfy the condition or not. So the total number of comparisons will be N*Q. Hence the overall time complexity is O(N*Q).

Space Complexity

O(1).

 

In this approach, ignoring the ‘ANS’ array , we are only using constant space. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Chocolate and Sweetness
Full screen
Console