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
DOT: 2018-08-17 22:17:07

I guess the test cases are weak, because I only employed sorting and compared the differences linearly in 2 loops, yet my code ran in 0.03s.

anubhav1772: 2017-07-14 21:03:33

Good Question :)

uddeshya2257: 2017-06-28 18:18:40

AC in one go....good use of sorting and binary search

Sigma Kappa: 2017-06-23 13:43:01

I've solved it in O(nlogn), basically for each position you do two binary searches.

onkar14_n: 2017-06-18 07:08:25

The problem is same as HACKRNDM

sir_zaid: 2017-02-11 06:20:34

nothing in the question,just use sets!

hugewarriors: 2016-12-28 14:54:45

AC in 1 Go.......!!!
sorting,,,,binary search!!!!

naman_ntc: 2016-12-07 06:22:57

i am getting time limit excedded. i guess its O(n^2) solution only!!

lalywr: 2016-07-25 09:47:11

a


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