Last Updated: 2 Apr, 2022
Count Pairs
Easy
Asked in companies
Given an array of integers ‘A’, and an integer ‘K’ find the number of happy elements.
Element ‘X’ is happy if there exists at least 1 element whose difference is less than ‘K’ i.e. an element ‘X’ is happy if there is another element in the range [X-K, X+K] other than ‘X’ itself.
For Example:
If N=3 and K=1 and array elements are [1,2,5].
For A[0], A[1] is the element that lies in the range [0,2] so, A[0] is the happy element.
For A[1], A[0] is the element that lies in the range [1,3] so, A[1] is the happy element.
For A[2], there is no element that lies in the range [4,6] other than A[2] so, A[2] is not the happy element.
Hence, the output will be 2.
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 will contain two space-separated integers ‘N’ and ‘K’, denoting the size of the array and the non-negative element.
The second line of each test case contains ‘N’ space-separated integers denoting elements of the array.
Output Format :
For each test case, print the number of happy elements in the array.
Print a separate line for each test case.
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 <= 10^4
0 <= K <= 10^5
-10^5 <= A[i] <= 10^5
Time limit: 1 sec
Approaches
The basic idea of this approach is for every element in the array to check for every other element in the array such that the absolute difference between them is less than or equal to ‘K’ except itself, if an element is found then increment the answer.
Here is the algorithm:
- Declare an integer “ans” initialize to 0.
- Iterate over the array “A” (say iterator ‘i’)
- Iterate over the array “A” (say iterator ‘j’)
- If ‘i’ is not equal to ‘j’ and abs(A[i]-A[j])<=k
- Increase “ans” by 1.
- break
- If ‘i’ is not equal to ‘j’ and abs(A[i]-A[j])<=k
- Iterate over the array “A” (say iterator ‘j’)
- Return ans.
For any element ‘x’ and the given integer ‘k’ we just have to find an element that lies in the range [x-k,x+k] except itself, The most probable element that lies in the range [x-k,x] is the element just smaller than or equal to ‘x’ and the most probable element that lies in the range [x,x+k] is the element just greater than or equal to ‘x’, if the array is sorted then we just have to check for two neighbouring elements of ‘x’.
Here is the algorithm :
- Declare an integer ‘ans’ initialize to 0.
- Sort the given array.
- Iterate over the array 'A' (say iterator ‘i’)
- If i-1>=0 and A[i]-A[i-1] is less than or equal to k
- ans+=1.
- Else if i+1 is less than n and A[i+1] - A[i] is less than or equal to k
- ans+=1.
- If i-1>=0 and A[i]-A[i-1] is less than or equal to k
- Return ans.