But I think the solution required is O(n) (one pass). So, O(nlogn) is not what the author wants anyway. Hashing is an option but we dont know the range of the elements in the array. So, in case when all keys hash into the same place, the worst case is still O(n^2). suppose our hash function is h(n) = n mod 10. array: 2,12,32,52,42.
On Fri, Jun 3, 2011 at 1:01 AM, Harshal <hc4...@gmail.com> wrote: > you can check if the element to be inserted next is same as the node value > while inserting itself. Why to do a separate inorder traversal.. > > > On Fri, Jun 3, 2011 at 12:56 AM, Supraja Jayakumar < > suprajasank...@gmail.com> wrote: > >> Hi >> >> Inserting into BST and break on same element will detect duplicates. >> But in any case, this is still O(2n) ? - once for inserting them in to the >> tree >> and another for the inorder read. >> >> Correct me if wrong. >> >> Rgds >> Supraja J >> >> >> On Thu, Jun 2, 2011 at 1:11 PM, Harshal <hc4...@gmail.com> wrote: >> >>> @Anurag: XOR wont work here, 1 element is repeated, not 1 element is >>> unique. Read the question again. >>> >>> Keep inserting elements in a BST and break once you find the same >>> element. O(nlogn) >>> >>> >>> On Fri, Jun 3, 2011 at 12:38 AM, Anurag Narain >>> <anuragnar...@gmail.com>wrote: >>> >>>> take X-OR of all the elements.....the one which has no duplicate will be >>>> left and rest all will be reduced to zero. >>>> >>>> -- >>>> 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. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> >>> >>> -- >>> Harshal Choudhary, >>> III Year B.Tech CSE, >>> NIT Surathkal, Karnataka, India. >>> >>> >>> -- >>> 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. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> U >> >> -- >> 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. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Harshal Choudhary, > III Year B.Tech CSE, > NIT Surathkal, Karnataka, India. > > > -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
