Count of Constraints

Moderate
0/80
0 upvote
Asked in company
Uber

Problem statement

Ninja loves to analyze the numbers of an array ‘ARR’ having ‘N’ elements. He thought of some ‘M’ numbers and an integer ‘D’. He wants to know who many numbers among these ‘M’ random numbers will satisfy the following equation:

Let the random number be ‘X’
| X- ARR[i] | > ‘D’ for ‘i’ in range 0 to length of ‘ARR’-1.

You are given an ‘ARR’ array having ‘N’ numbers, another array ‘B’ having ‘M’ numbers, and integer ‘D’. Your task is to find the count of numbers among array ‘B’ satisfying the given condition.

For Example 
For the given ‘ARR’ = [ 13,1,4 ] and B=[7,6,9] and ‘D’=3, the answer will be 1 as only 9 satisfies the given condition among the given numbers.
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 three integers, 'N’ denoting the number of numbers in array ‘ARR’, ‘M’ representing the number of elements in array ‘B’, and integer ‘D’.

The second line contains ‘N’ numbers denoting the numbers in the array ‘ARR’.

The third line contains ‘M’ numbers denoting the numbers in array ‘B’.
Output Format: 
For each test case, print a single integer denoting the count of numbers among array ‘B’ satisfying the given condition.  

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 <= 5000.
1 <= M <= 5000.
1 <= D <= 1000.
1 <=ARR[i] <= 10^6
1 <=B[i] <=10^6. 

Time limit: 1 sec
Sample Input 1:
2
4 3 1
3 5 4 6 
2 1 8
3 3 3
13 1 4
7 6 9
Sample Output 1:
2
1
Explanation of sample input 1:
For the first test case,
The difference between 3 and 2 is 1, which is not greater than 1. So 2 doesn’t satisfy the given condition.
The absolute difference between 1 and all elements of ‘ARR’ is greater than ‘D’.So 1 satisfies the given condition.
The absolute difference between 8 and all elements of ‘ARR’ is greater than 1. So 8 satisfies the condition.
So there are 2 numbers among ‘B’ which follows the condition. Hence the answer is 2.

For the second test case:
The absolute difference between 7 and 4 is 3, which is not greater than 3. So 7 doesn’t satisfy the condition.
The absolute difference between 6 and 4 is 2, which is not greater than 3. So 6 doesn’t fulfill the condition.
The absolute difference between 9 and all elements of ‘ARR’ is greater than 3. So 9 satisfies the given condition.
So there is only 1 number among ‘B’, which follows the condition. Hence the answer is 1.
Sample Input 2:
2
3 3 2
8 4 5 
3 10 6
5 3 3
10 12 0 8 0 
4 3 8
Sample Output 2:
0
1
Hint

Check the absolute difference of random number with all elements of ‘ARR’.

Approaches (2)
Brute Force.

In this approach, we will check the absolute difference of each element of ‘B’ with all elements of ‘ARR’. If All the absolute difference’s value for B[i] is greater than ‘D’ we found a number that fulfills the given condition. So we increment the answer count by 1.

  

Algorithm:

  • Declare ‘ANS’ to store the count of numbers among ‘B’ satisfying the condition.
  • Set ‘ANS’ as 0.
  • For an index i in range 0 to ‘M’-1, do the following:
    • Set ‘IS_GOOD’ as true.
    • For j in range 0 to ‘N’-1, do the following:
      • Set ‘VAL’ as absolute of (B[i] - ‘ARR’[j]).
      • If ‘VAL’ is less than or equal to ‘D’:
        • B[i] does not fulfill the condition.
        • Set ‘IS_GOOD’ as false.
        • Break the loop.
    • If ‘IS_GOOD’ is true:
      • Set ‘ANS’ as ‘ANS’ +1.
  • Return ‘ANS’.
Time Complexity

O(N*M), where ‘N’ is the number of elements in array ‘ARR’ and ‘M’ is the number of elements in array ‘B’.

 

In this approach, for each number in ‘B’, we calculate its absolute difference with all ‘ARR’ numbers. So the total number of operations is M*N. Hence the overall time complexity is O(N*M).

Space Complexity

In this approach, we have used constant space. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Count of Constraints
Full screen
Console