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
asifalim: 2020-11-30 19:09:21

accept in 1st attempt using trial and error algo

kartik170901: 2020-07-08 00:50:33

it is 2 pointer for O(n) why would one use binary search O(nlogn)

Last edit: 2020-07-08 00:50:47
kumar_anubhav: 2020-06-20 09:38:45

AC in one go !! binary search is faster than hashmap :))

pissedoff: 2020-05-18 09:09:10

Input described in Problem is wrong. Input takes values in "n" separate lines.
Cost me 2 NZEC.

wowthecoder: 2020-05-16 10:30:22

I used Scanner and Arrays.binarySearch() to solve this in Java, AC in 1.22 sec... I thought the limit was 1 sec?
When I tried to refine my answer by changing from Scanner to BufferedReader and StringTokenizer, I always get wrong answer/runtime error(NZEC)...I don't understand

mrmajumder: 2020-04-16 13:26:02

Easy problem to practice sliding window technique

sunnyrathee: 2020-04-14 13:18:11

Try to implement by BINARY SEARCH

suyashky: 2020-01-29 23:24:45

The wrong Solution got AC!
Realized while solving OPCPIZZA.

shikhar_may7: 2019-10-19 22:20:19

wtf is with this question... cin, cout , sorted vectors result TLE; scanf, printf sorte array gives AC...!!!

emtiaz_001: 2019-09-22 15:20:20

very easy . good for beginner


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