PAIRS1 - Count the Pairs


Given N integers [0 < N <= 10^5], count the total pairs of integers that have a difference of K. (Everything can be done with 32 bit integers).

Input

1st line contains integers N and K.

2nd line contains N integers of the set. All the N numbers are distinct.

Output

One integer - the number of pairs of numbers that have a difference of K.

Example

Input:
5 2
1 5 3 4 2

Output:
3
Input:
10 1
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793

Output:
0

hide comments
ekram: 2021-11-21 07:45:08

//What is the wrong for this code
<snip>

[NG]: Read the footer.

Last edit: 2021-11-21 13:29:50
dewasemadi: 2021-01-13 01:20:09

AC in a go..!

it_uchi: 2021-01-09 21:22:01

AC in a GO.
1. Sort and BS
2. Hash Map

pavit_1809: 2020-04-20 18:40:49

Merge sort can also be applied as we are only supposed to check every pair and merge sort would do that in O(nlogn) time complexity.

ajaygupta007: 2020-04-09 21:30:42

solved using both techinques
1.hashmap
2.sorting,binary search

scolar_fuad: 2019-11-27 18:22:58

just fix a number then find upper bound and lowerbound for every number+k

selisahil: 2019-09-25 16:22:20

use hashing....

jinks: 2019-09-17 08:05:24

why is sorting +binary search give runtime error?

lx_lovin: 2019-08-09 05:03:11

without sorting and binary search just do mapping
O(n) solution only 6 lines of code

Last edit: 2019-08-09 05:04:58
kushagra_2: 2019-01-22 17:17:43

Sort + binary search O(nlogn) AC in one go!!


Added by:psn
Date:2013-10-18
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own