Count Pairs

Easy
0/40
profile
Contributed by
0 upvote
Asked in companies
HCL TechnologiesGoogle inc

Problem statement

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.
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 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
Sample Input 1 :
2
2 0
3 3 
3 1
1 2 5
Sample output 1 :
2
2
Explanation For Sample Output 1:
For the first test case,
N=2 and K=0 and array elements are [3,3]. 
For A[0], A[1] is the element that lies in the range [3,3] so, A[0] is the happy element.
For A[1], A[0] is the element that lies in the range [3,3] so, A[1] is the happy element.
Hence, the output will be 2.

For the second test case,
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.
Sample Input 2 :
2
3 7
7 3 5 
2 3
3 1
Sample output 2 :
3
2
Hint

For every element in the array check for every other element in the array except itself.

Approaches (2)
Brute Force

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:

  1. Declare an integer “ans” initialize to 0.
  2. 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
  3. Return ans.
Time Complexity

O( N ^ 2 ), where ‘N’ is the size of the array.

 

For every element in the array, we check for every other element in the array.

So time complexity will be O( N^2 ).

Space Complexity

O( 1 )

 

We are not using any extra space.

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