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
bhanu_546: 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

stardust2003: 2024-01-26 06:59:13

how to implement binary search here?

reyan007: 2022-10-05 22:55:24

@kartik170901 it is O(nlogn) for two pointer .

rangey_18o3_20: 2021-07-15 17:40:56

Think about the number of pairs for n=10^5.

mkrishnasai: 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.

satyam_656: 2021-06-05 15:23:07

smiply use map

muzairs: 2021-03-21 13:32:35

https://www.spoj.com/submit/HACKRNDM/id=27584170
pls tell whats wrong

makhan_28: 2021-03-18 14:16:01

Solved it with 2-pointer!! :)

muzairs: 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
majid: 2021-02-13 10:46:50

Input described in Problem is wrong. Input takes values in "n" separate lines.


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