@Yasir: Sort the numbers. Then
int i = 0, j = 1, m, p = 0;
while( j < N )
{
m = a[j] - a[i];
if( m = K )
++p;
else if( m < K )
++j;
else
++i;
}
// answer = p
Complexity = O(n log n).
Dave
On Aug 7, 12:53 pm, Yasir <[email protected]> wrote:
> Guys,
> Let's try to find out an efficient solution for the following prob:
>
> 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.
> 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.
>
> PS: Note that n is very large, so try to come up with an efficient
> solution. :)
>
> Source:http://www.interviewstreet.com/recruit/challenges/dashboard/
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
