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

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

hide comments
2024-06-11 14:09:58
idea:for each ele add k and binary search in array as only 1 possiblity and looking forward across array back ones are calculated
2024-01-26 06:59:13
how to implement binary search here?
2022-10-05 22:55:24
@kartik170901 it is O(nlogn) for two pointer .
2021-07-15 17:40:56
Think about the number of pairs for n=10^5.
2021-06-21 17:27:54
In Java don't use 'BufferedReader' because the input format is not as mentioned, so it's resulting in Runtime error (NZEC) try 'Scanner' instead it executes within the given time limit.
2021-06-05 15:23:07
smiply use map
2021-03-21 13:32:35
https://www.spoj.com/submit/HACKRNDM/id=27584170
pls tell whats wrong
2021-03-18 14:16:01
Solved it with 2-pointer!! :)
2021-03-04 08:26:46
can ysomeone spot whats wrong with my code

[NG]: Read the footer.

Last edit: 2021-03-04 11:51:02
2021-02-13 10:46:50 majid
Input described in Problem is wrong. Input takes values in "n" separate lines.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.