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
aeonflux: 2016-06-22 21:02:21

AC...binary search

siddharth: 2016-06-20 12:30:31

Simple use of maps did it for me. No sorting and binary search required.
AC in 1 go

shubham2305: 2016-06-07 18:47:36

preety easy
AC in 1 go for BOTH the cases
1st tried using brute force O(n);
2nd tried quicksort +binary search O(nlgn);

mkfeuhrer: 2016-06-06 12:56:43

stl .. binary_search... AC in 1 go :-)

citransvostok: 2016-06-04 16:42:36

K >= 0,
costed me 5 WAs

maala_m: 2016-05-06 14:36:06

14 Line code run in 0.08 second was enough to solve this task :)

Last edit: 2016-05-06 14:40:32
Christian López: 2016-04-27 18:05:01

Fast I/O + qsort + Brute force = AC in 0.04

Don't use std::vector.

sohumshah: 2016-03-19 11:40:46

why time limit exceeded error?

nightwolf_9197: 2016-03-11 21:41:11

fast i/o +qsort +brute force=AC in 0.04s

pvsmpraveen: 2016-01-31 14:45:13

STL Rocks!


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