Count Pairs Problem (TCS Codevita)

July 21, 2021

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

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

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

Java

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

Positive or Negative number: C | C++ | Java
Even or Odd number: C | C++ | Java
Sum of First N Natural numbers: C | C++ | Java
Sum of N natural numbers: C | C++ | Java
Sum of numbers in a given range: C | C++ | Java
Greatest of two numbers: C | C++ | Java
Greatest of the Three numbers: C | C++ | Java
Leap year or not: C | C++ | Java
Prime number: C | C++ | Java
Prime number within a given range: C | C++ | Java
Factorial of a number: C | C++ | Java
Sum of digits of a number: C | C++ | Java
Reverse of a number : C | C++ | Java
Palindrome number: C | C++ | Java
Armstrong number : C | C++ | Java
Armstrong number in a given range : C | C++ | Java
Fibonacci Series upto nth term : C | C++ | Java
Factorial of a number : C | C++ | Java
Power of a number : C | C++ | Java
Factor of a number : C | C++ | Java
Strong number : C | C++ | Java
Perfect number : C | C++ | Java
Automorphic number : C | C++ | Java
Harshad number : C | C++ | Java
Abundant number : C| C++ | Java
Friendly pair : C | C++ | Java