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
wisfaq: 2017-05-27 13:59:35

Python users be careful: the n elements of the set are all on a separate line!

ajeetk_973: 2017-03-31 00:51:39

AC in one go///// simple sort and two pointer game///

amalik123: 2017-03-15 09:58:45

simple use of binary search

nilabja16180: 2017-03-09 08:27:36

AC in one GO!
Sort + binary search works like charm!

da_201501181: 2017-02-12 14:01:27

Easy..!! AC in one Go!! using java.util.HashMap;

aeon: 2016-12-11 20:07:13

if you are using unordered_map and c++ as your submission language use c++14(g++5.1), other versions cost me 1 compilation Error.

jawad_cs: 2016-12-10 05:36:45

map-O(nlogn+n)-0.13
unordered_map-O(n)-0.05
binarysearch-O(nlogn+nlogn)-0.04 (but why did nlogn solution took less time than O(n)...i don't get it)

p_kr: 2016-10-25 18:34:13

AC in C++
-- binary Search 0.04 sec O(N * log(N) + N*log(N) )
-- two pointers with sort 0.03 sec O(N * log(N) + N)

Last edit: 2016-10-25 18:35:40
syed_tanveer: 2016-10-25 14:29:26

Very easy with maps, will try the trivial binary search approach too. :)

bartol3141: 2016-10-21 17:53:22

lower_bound
AC in one go :]


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