Prime #### Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime #### Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

# Count Pairs Problem (TCS Codevita)

## Count Pairs Problem

Count Pairs Problem is a simple array manipulation coding problem which was asked in TCS Codevita coding competition. TCS organizes this global level coding competition in order to promote Porgramming-As-a-Sport in the search of world’s best Coder.This is an article on TCS Codevita Count Pairs Problem where we have to find the number of happy elements in an array. ### Problem Description

Given an array of integers A, and an integer K find 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.

Constraints

• 1 <= N <= 10^5
• 0 <= K <= 10^5
• 0 <= A[i] <= 10^9

Input

• First line contains two integers N and K where N is size of the array and K is a number as described above.
• Second line contains N integers separated by space.

Output

• Print a single integer denoting the total number of happy elements.

Example 1

Input

6 3

5 5 7 9 15 2

Output

5

Explanation

Other than number 15, everyone has at least 1 element in the range [X-3, X+3]. Hence they are all happy elements. Since these five are in number, the output is 5.

Example 2

Input

3 2

1 3 5

Output

3

Explanation

All numbers have at least 1 element in the range [X-2, X+2]. Hence they are all happy elements. Since these three are in number, the output is 3.

Possible Solution

Input:

3 2

1 3 5

`import java.util.*;class Main {    public static int solve (int arr[], int n, int k)     {        int count = 0;        for (int i = 0; i < n; i++)        {            int a = arr[i];            int id1 = i;            int id2 = i;            if (i == 0)    	    {                while (arr[id2 + 1] == a)                    id2 += 1;                if (arr[id2 + 1] <= a + k && arr[id2 + 1] >= a - k)                    count += 1;            }        	else if (i < n - 1)    	    {                while (arr[id2 + 1] == a)                    id2 += 1;                while (arr[id1 - 1] == a)                    id1 -= 1;                if (((arr[id1 - 1] <= a + k) && (arr[id1 - 1] >= a - k))|| ((arr[id2 + 1] <= a + k) && (arr[id2 + 1] >= a - k)))                    count += 1;            }		    else    	    {                while (arr[id1 - 1] == a)                    id1 = id1 - 1;	                   if (arr[id1 - 1] <= a + k && arr[id1 - 1] >= a - k)                    count += 1;            }        }        return count;    }      public static void main (String[]args)     {        Scanner sc = new Scanner (System.in);        int n = sc.nextInt ();        int k = sc.nextInt ();        int arr[] = new int[n];            for (int i = 0; i < n; i++)            arr[i] = sc.nextInt ();        Arrays.sort (arr);            System.out.println (solve (arr, n, k));    } }` 