PAIRS1 - Count the Pairs


 

Given N integers [N<=10^5], count the total pairs of integers that have a difference of K. [K>0 and K<1e9]. Each of the N integers will be greater than 0 and at least K away from 2^31-1 (Everything can be done with 32 bit integers).
Input Format
1st line contains N & K (integers).
2nd line contains N numbers of the set. All the N numbers are assured to be distinct.
Output Format
One integer saying the number of pairs of numbers that have a diff K.
Sample Input #00:
5 2  
1 5 3 4 2  
Sample Output #00:
3
Sample Input #01:
10 1  
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 
Sample Output #01:
0

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 Format

 

1st line contains N & K (integers).

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

 

Output Format

 

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

 

Sample Input :

5 2  

1 5 3 4 2  

Sample Output :

3

Sample Input :

10 1  

363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 

Sample Output :

0

 


hide comments
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!!

atharvat77: 2019-01-04 17:01:31

Good Question To Apply Binary Search

Last edit: 2019-01-04 17:01:48

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