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

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

hide comments
2019-01-04 17:01:31
Good Question To Apply Binary Search


Last edit: 2019-01-04 17:01:48
2018-08-27 08:27:34
all nos are not distinct
2018-08-17 22:17:07 DOT
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.
2017-07-14 21:03:33
Good Question :)
2017-06-28 18:18:40
AC in one go....good use of sorting and binary search
2017-06-23 13:43:01 Sigma Kappa
I've solved it in O(nlogn), basically for each position you do two binary searches.
2017-06-18 07:08:25
The problem is same as HACKRNDM
2017-02-11 06:20:34
nothing in the question,just use sets!

2016-12-28 14:54:45
AC in 1 Go.......!!!
sorting,,,,binary search!!!!
2016-12-07 06:22:57
i am getting time limit excedded. i guess its O(n^2) solution only!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.