@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 <dave_and_da...@juno.com> 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 <amolsharm...@gmail.com> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
