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
aryan29: 2019-06-03 18:24:36

using maps will do the job AC in one go

adarsh313: 2019-03-09 16:11:08

little change in OPCPIZZA and AC

kushagra_2: 2019-01-10 14:20:38

that's why i love binary search AC in 0.04 sec:)

pavan_bansal: 2018-12-13 21:15:30

AC in one go!!!

salman3007: 2018-10-03 15:21:36

observations:
1. int arr[] is better than vector<int> arr.
2.scanf and printf are better than cin and cout

ameyanator: 2018-09-25 12:03:02

C++STL or binary search take your pick!

prince_jain: 2018-07-26 23:30:15

try to do binary search iteratively, recursive approach will give TLE

jmr99: 2018-06-18 11:33:09

1.no binary search,no 2 pointer,no sorting just map<int,int>
AC !! 0.19
2. binary search AC !! 0.07

kuchnahiaata: 2018-03-30 22:09:00

sorting + O(n), no binary search, no two pointer
AC 0.03

Last edit: 2018-03-30 22:12:32
dheeraj161: 2018-03-10 14:48:21

AC IN ONE GO :) very easy


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