Sunday 27 May 2012

InterviewStreet CouponDunia Count Pairs Problem: C++ code


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 2

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

Sample Output #01:
 
 
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) 
 
 

4 comments:

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

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

    ReplyDelete
  3. def pdiff(arr,k)
    a= arr.combination(2).to_a
    a.select! {|i| ((i[0] - i[1]) == k || (i[1] - i[0]) == k)}
    a.length
    end

    ReplyDelete