@ankit and lingerdave.... How does hashing help here ?? i say we have to create an array size which is there range of the numbers...else it cant be solved in O(n)
Hashing is not helpful here in worst case hashing may lead to a O(n2) solution as all the keys may hash into the same place eg.. 4,14,24,34,44,4 if h(n)= n mod 100 On Sun, Oct 10, 2010 at 5:51 PM, Mridul Malpani <[email protected]>wrote: > can this problem be solved in O(n) time and in O(1) space? > > On Oct 6, 10:41 pm, ligerdave <[email protected]> wrote: > > @mukesh, nope, you do not need to know the range. are you thinking > > about array? ankit's solution is the implementation of "bucket" > > logic. > > > > On Oct 6, 11:47 am, Mukesh Gupta <[email protected]> wrote: > > > > > @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]> > <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%[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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.
