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

hide comments
ivar.raknahs: 2014-10-06 13:43:03

this ques really annoyed me .
After 1 tle and 6 runtime error finally AC

fanatique: 2014-08-20 07:25:13

my 100th :) but i am crawling :(

shiva: 2014-08-13 15:05:16

TLE nlogn :(

Darren Sun: 2014-08-08 10:51:19

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
Satyaki Upadhyay: 2014-07-01 06:41:13

How is it that O(n) solution takes more time than O(nlogn) solution? o_O

L: 2014-06-26 13:16:35

O(n) sol'n takes 1.63secs but AC
why?

Rishab Banerjee: 2014-04-27 15:16:48

STL u r great :-)

@N)R3$: 2014-02-25 00:41:53

good problem :D AC to the first

Vishal Gautam: 2013-09-20 17:45:59

getting segmentation fault.. can anyone give me strong test case


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