How about iterating over all the values and hashing them to a dict/map. And then iterate once more, checking that for each element 'e', |K-e| exists in the map or not. O(N)?
On Sun, Aug 7, 2011 at 10: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. > > -- Shuaib http://www.bytehood.com http://twitter.com/ShuaibKhan -- 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.
