Please login

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.

Count pairs

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));
}
}