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
2014-10-06 13:43:03 ivar.raknahs
this ques really annoyed me .
After 1 tle and 6 runtime error finally AC
2014-08-20 07:25:13 fanatique
my 100th :) but i am crawling :(
2014-08-13 15:05:16 shiva
TLE nlogn :(
2014-08-08 10:51:19 Darren Sun
An O(n) solution might be slower than an O(n*logn) one for some given input. Constant factor also plays a role. For example, computing a hashcode costs constant time, but the overall time for computing hashcodes of n numbers might be significant. Besides, some time is wasted in re-allocating large amount of space and data migration. This is especially the case for the rehash scenario when a hash table is used.

P.S. With optimized I/O, Java solution with O(n*logn) suffices to get accepted.

Last edit: 2014-08-08 10:58:04
2014-07-01 06:41:13 Satyaki Upadhyay
How is it that O(n) solution takes more time than O(nlogn) solution? o_O
2014-06-26 13:16:35 L
O(n) sol'n takes 1.63secs but AC
why?
2014-04-27 15:16:48 Rishab Banerjee
STL u r great :-)
2014-02-25 00:41:53 @N)R3$
good problem :D AC to the first
2013-09-20 17:45:59 Vishal Gautam
getting segmentation fault.. can anyone give me strong test case
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.