@Ankit: Insertion in hashmap in O(n) in worst case. As long as range of the numbers is not known we cannot predict whether the algo will run in linear time. Any other idea for O(n)??
Mukesh Gupta Delhi College of Engineering On Wed, Oct 6, 2010 at 4:32 PM, sourav <[email protected]> wrote: > @Mukesh > > Thanks for your attempt. But the question asks for liner or sublinear > solution. > > Sourav > > On Oct 6, 3:50 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%[email protected]> > . > > > 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%[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.
