yes, it can be done in O(n). think about the logic working behind bucket sort. we assume in this problem, memory space is inf all you need to do is put all numbers in its own "bucket" when a number was pushed into one bucket which had already been occupied, you have the duplicated number there. when you run to n-1 number, you know all the numbers so far are unique(coz duplication hadn't happened). by definition of the problem, you have only one duplicated number. therefore, the last number is duplicated. O(2(n-1)) > O(n)
On Oct 6, 7:08 am, tech rascal <[email protected]> wrote: > can u do dis problem in linear time, o(n)?? > > On Wed, Oct 6, 2010 at 4:20 PM, Mukesh Gupta > <[email protected]>wrote: > > > > > Keep inserting elements in a binary search tree and break once you get > > the find the element in the tree. > > Complexity=O(n log n) > > > On 10/5/10, sourav <[email protected]> wrote: > > > You are given an array of positive numbers in which one number is > > > repeated. Rest all are present only once. Find the duplicate number in > > > linear or sub linear time. > > > > -- > > > 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]<algogeeks%2bunsubscr...@googlegroups > > > .com> > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > -- > > > Mukesh Gupta > > Delhi College of Engineering > > > -- > > 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]<algogeeks%2bunsubscr...@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 [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.
