correction about that example h(n)= n mod 10 On Fri, Oct 15, 2010 at 10:23 PM, nishaanth <nishaant...@gmail.com> wrote:
> @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 > <malpanimri...@gmail.com>wrote: > >> can this problem be solved in O(n) time and in O(1) space? >> >> On Oct 6, 10:41 pm, ligerdave <david.c...@gmail.com> 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 <mukeshgupta.2...@gmail.com> 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 <souravs...@gmail.com> wrote: >> > > > @Mukesh >> > >> > > > Thanks for your attempt. But the question asks for liner or >> sublinear >> > > > solution. >> > >> > > > Sourav >> > >> > > > On Oct 6, 3:50 pm, Mukesh Gupta <mukeshgupta.2...@gmail.com> 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 <souravs...@gmail.com> 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 algogeeks@googlegroups.com >> . >> > > > > > To unsubscribe from this group, send email to >> > > > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> <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 algoge...@googlegroups.com. >> > > > To unsubscribe from this group, send email to >> > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> <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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > S.Nishaanth, > Computer Science and engineering, > IIT Madras. > -- 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 algoge...@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.
