HACKRNDM - Hacking the random number generator

You recently wrote a random number generator code for a web application and now you notice that some cracker has cracked it. It now gives numbers at a difference of some given value k more predominantly. You being a hacker decide to write a code that will take in n numbers as input and a value k and find the total number of pairs of numbers whose absolute difference is equal to k, in order to assist you in your random number generator testing.

NOTE: All values fit in the range of a signed integer, n, k>=1

Input

1st line contains n & k.
2nd line contains n numbers of the set. All the n numbers are assured to be distinct.

(Edited: n <= 10^5)

Output

One integer saying the no of pairs of numbers that have a diff k.

Example

Input:
5 2
1 5 3 4 2 Output: 3

Added by:vijay
Date:2011-10-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2013-08-29 19:06:38 Aswin Murugesh
@vijay: The same algorithm gives AC in c++ and WA in python. Why is it so?
2013-08-24 01:47:52 Anant Kumar
Didn't knew long long takes more memory as well as more time!!!
2013-08-20 14:17:06 Mahesh Mishra
long long int - TLE unsigned int - AC
2013-09-23 14:33:24 @Shish
:D very easy using sorting + searching

Last edit: 2013-08-19 10:56:53
2013-07-22 10:31:43 Luka
very irritated !! :'( was printing the contents of the sorted array for my own convenience, costed me 8-9 WAs and then had not inserted \n at the end of printing-- 1 WA.. In all, 10 WA's and then an AC :D
2013-07-03 16:02:28 Sayan Paul
getting NZEC error ..plz help
2013-05-27 22:28:47 Spar!k
I don't think that O(n) algorithm exists unless the numbers are small. (<= ~10^7)
2013-05-19 13:18:43 Chandan Mittal
finally got AC :) with mergesort and binary search
2013-05-05 07:38:00 Ouditchya Sinha
Piece of cake, AC in 0.10s :)
2013-03-21 17:35:53 Eduardo Nunes
lol,
solution O(n*log(n)): 1.19 sec;
solution O(n): 1.36 sec... o_O
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.