any other solution other than hashing....bcoz say numbers are very very large....ya....i want a linear solution....
i first choice was also hashing.....but the interviewer wanted something other than that... -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad <http://gplus.to/amolsharma99> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/> On Fri, Feb 17, 2012 at 9:39 AM, atul anand <[email protected]> wrote: > @amol : actually complexity you have asked for is like saying finding > solution in linear time. because we need to traverse whole array once > atleast to find the solution and total size of array is n*k+b=N. so > required complexity is O(N). > > so we can use hashmap to solve this problem. > > > > On Fri, Feb 17, 2012 at 4:19 AM, Dave <[email protected]> wrote: > >> @Amol: Since you don't restrict using extra space, use hashing or do a >> radix sort, either being O(n*k+b). >> >> Dave >> >> On Feb 15, 12:07 pm, Amol Sharma <[email protected]> wrote: >> > Given an array of size n*k+b.In this array n elements are repeated k >> times >> > and 1 elements are repeated b times.find the Elements which is repeated >> b >> > time.( O(n*k+b) expected ) >> > -- >> > >> > Amol Sharma >> > Third Year Student >> > Computer Science and Engineering >> > MNNIT Allahabad >> > <http://gplus.to/amolsharma99> >> > <http://twitter.com/amolsharma99>< >> http://in.linkedin.com/pub/amol-sharma/21/79b/507>< >> http://www.simplyamol.blogspot.com/> >> >> -- >> 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. >> >> > -- > 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. > -- 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.
