@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.
