Last Updated: 27 Sep, 2021

Count of Constraints

Moderate

Asked in company

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.

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

Solve now

Approaches

01 Approach

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’.

Solve now

02 Approach

If we observe the given equation, we can conclude that any number ‘X’ doesn’t satisfy the equation if there is any number in ‘ARR’ in range ‘X’-’D’ to ‘X’+’D’(both inclusive). Otherwise, the number ‘X’ satisfies the condition.

In this approach, we will first sort the ‘ARR’ array so that we can apply binary search over it.

For each number in ‘B’, we will find the number just greater than B[i] and just smaller than B[i] in array ‘ARR’.And if any of these two numbers lies in this range (B[i] -D, B[i]+D),B[i] fails the condition.Otherwise, we will increment ‘ANS’.

Algorithm:

Declare ‘ANS’ to store the count of numbers among ‘B’ satisfying the condition.
Set ‘ANS’ as 0.
Sort the array ‘ARR’.
For an index i in range 0 to ‘M’-1, do the following:
- ‘LESS_VALUE’ will store the value just less than B[i] in ‘ARR’.
- Set ‘LESS_VALUE’ as -1.
- ‘GREATER_VALUE’ will store the value just greater than B[i] in ‘ARR’.
- Set ‘GREATER_VALUE’ as -1.
- Set ‘IS_GOOD’ as true.
- Set the values of ‘LESS_VALUE’ and ‘GREATER_VALUE’ using the inbuilt binary search function.
- If ‘IS_LESS’ is not equal to -1 and ‘IS_LESS’ is greater than equal to ‘B[i]-D’:
  - Set ‘IS_GOOD’ as false.
- If ‘IS_GREATER’ is not equal to -1 and ‘IS_GREATER’ is less than equal to ‘B[i]+D’:
  - Set ‘IS_GOOD’ as false.
- If ‘IS_GOOD’ is true:
  - Set ‘ANS’ as ’ANS’ +1.
Return ‘ANS’.

Solve now