First sort the array.Then for each element,say x ,do a binary search to find the element y for which (y-x)=K or y=(x+K),if the elements are not distinct then the number of pairs will be the upper_bound()-lower_bound() for y. Complexity:O(nlogn)
On Sun, Aug 7, 2011 at 11:23 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. > > -- *Regards,* *Piyush Kapoor,* *2nd year,CSE IT-BHU* -- 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.
