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
2016-01-27 15:59:28
java -> 0.23 secs AC
2015-12-31 09:22:08
Fast I/O + Qsort + Binary Search = AC but still time was 0.08 seconds. Later will give it a try using a method similar to sliding window / 2 pointers. Maybe that will help the time limit.
2015-12-18 11:11:13
simple one....O(n) solution
2015-12-08 12:49:20
0.04s using the two pointers method. Even faster than binary search as the time complexity is only O(n) instead of O(nlogn).

Last edit: 2015-12-08 12:50:42
2015-11-28 14:18:39 Prateek Agarwal
binary search 0.04s 3.7M
STL 0.11s 9M
2015-11-04 11:35:00 danish_shark
worked in 0.26 secs. O(n) using java.util.HashMap :)
2015-08-25 17:59:32
venkatesh, you have to check for element-k as well
2015-08-17 23:51:47 ASHUTOSH DWIVEDI
quick sort + binary search ==> AC..
2015-08-06 05:37:46 venkatesh
I am getting WA in python. Can someone tell me, what is wrong?
I am using sets for checking element + k is exist or not?


Last edit: 2015-08-06 05:49:08
2015-08-05 08:18:07 venkatesh
set is good
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.