PAIRS1 - Count the Pairs


Given N integers [0 < N <= 10^5], count the total pairs of integers that have a difference of K. (Everything can be done with 32 bit integers).

Input

1st line contains integers N and K.

2nd line contains N integers of the set. All the N numbers are distinct.

Output

One integer - the number of pairs of numbers that have a difference of K.

Example

Input:
5 2
1 5 3 4 2

Output:
3
Input:
10 1
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793

Output:
0

hide comments
atharvat77: 2019-01-04 17:01:31

Good Question To Apply Binary Search

Last edit: 2019-01-04 17:01:48
sudhanshu6324: 2018-08-27 08:27:34

all nos are not distinct

DOT: 2018-08-17 22:17:07

I guess the test cases are weak, because I only employed sorting and compared the differences linearly in 2 loops, yet my code ran in 0.03s.

anubhav1772: 2017-07-14 21:03:33

Good Question :)

uddeshya2257: 2017-06-28 18:18:40

AC in one go....good use of sorting and binary search

Sigma Kappa: 2017-06-23 13:43:01

I've solved it in O(nlogn), basically for each position you do two binary searches.

onkar14_n: 2017-06-18 07:08:25

The problem is same as HACKRNDM

sir_zaid: 2017-02-11 06:20:34

nothing in the question,just use sets!

hugewarriors: 2016-12-28 14:54:45

AC in 1 Go.......!!!
sorting,,,,binary search!!!!

naman_ntc: 2016-12-07 06:22:57

i am getting time limit excedded. i guess its O(n^2) solution only!!


Added by:psn
Date:2013-10-18
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own