CouponDunia Count Pairs Problem

**Problem Statement**Given N numbers , [N<=10^5] we need to count the total pairs of numbers

that have a difference of K. [K>0 and K<1e9]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 no of pairs of numbers that have a diff K.Sample Input #00:5 2 1 5 3 4 2Sample Output #00:3

Sample Input #01:10 1 363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793Sample Output #01:0

Solution

` `

#include<iostream> #include<algorithm> using namespace std; int compare (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } int main() { int n,k; cin>>n>>k; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; qsort(a,n,sizeof(int),compare); int seq=0; for(int i=0;i<n;i++) { int key=a[i]+k; if(((int*)bsearch(&key,a+i+1,n-i-1,sizeof(int),compare))!=NULL) seq++; }

cout<<seq; }

` `

` `

**Time Complexity **: O(nlogn)

the complexity of the above algorithm is O(nlogn)[for sorting]+ O(nlogn)[n binary search = O(nlogn)]

ReplyDeletethe complexity of the above algorithm is O(nlogn)[for sorting]+ O(nlogn)[n binary search = O(nlogn)]

ReplyDeletethanks.

Deletedef pdiff(arr,k)

ReplyDeletea= arr.combination(2).to_a

a.select! {|i| ((i[0] - i[1]) == k || (i[1] - i[0]) == k)}

a.length

end