@nishaanth hashing=O(n^2)? what kinda of hashing are we talking about?
array w/ range of the numbers? you meant smallest and the biggest? so you have to scan through the given numbers first to find the range. if you scanned, why not find the duplication in the first place? okay, lets say you are given the smallest and the biggest. 4 and 44, you would have an array size that's more than the size of given numbers. what if the given set is 1, 1000000, 1? On Oct 15, 12:53 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 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. > > > > > > > -- > > > > > > > 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. -- 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.
