you can use Java HashTable/HashMap to store key value pair, where Key being the element stored in array and Value being the index of the element. Any duplicate insert on key will replace the value of that Key. After finishing all elements retrieve all Key, value pair stored in HashMap.
Let me know If I am missing something!! But if you want to make your own hashtable. Then we can find the range of elements in one pass and then carefully choose some hash function to avoid collision and make hash on key. But this will not be one pass. On Fri, Jun 3, 2011 at 7:31 AM, D.N.Vishwakarma@IITR <deok...@gmail.com> wrote: > @Sanjay ahuja > yes ans is required in O(n) > how it can be done by hashing? > > On Fri, Jun 3, 2011 at 1:19 AM, Supraja Jayakumar <suprajasank...@gmail.com> > wrote: >> >> Hi >> >> I think multi hash table will solve this problem. >> >> Thanks >> Supraja J >> >> On Thu, Jun 2, 2011 at 1:37 PM, Harshal <hc4...@gmail.com> wrote: >>> >>> 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. >> >> >> >> -- >> 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. > > > > -- > With Regards > Deoki Nandan Vishwakarma > IITR MCA > Mathematics Department > > -- > 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. > -- Sanjay Ahuja, Analyst, Financing Prime Brokerage Nomura Securities India Pvt. Ltd -- 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.
