yes , but that constraint is not provided by the interviewer , hence , solution of hash is not acceptable
On Fri, Aug 19, 2011 at 8:58 AM, Dheeraj Sharma <dheerajsharma1...@gmail.com > wrote: > hash map is the solution provided the elements lie in a predefined range.. > > On Fri, Aug 19, 2011 at 8:46 AM, *$* <gopi.komand...@gmail.com> wrote: > >> true. I agree , we can use additional memory which will be constant >> irrespective of counjt of elements. >> >> But using an hash wont be a constant memory as input can keep on varying. >> >> Thx, >> --Gopi >> >> >> On Fri, Aug 19, 2011 at 8:16 AM, Dipankar Patro <dip10c...@gmail.com>wrote: >> >>> O(1) space means constant space. It doesn't mean you can't use extra >>> space. >>> Refer here: >>> http://stackoverflow.com/questions/2219109/what-does-this-mean-on-steps-and-o1-space >>> >>> According to the question you can definitely use a Hash Table for keeping >>> hit record, as it will be a constant space (provided the range of numbers is >>> known). >>> >>> In case the range of numbers is not known, BST will be close answer. >>> Since only one element will be repeating, the process of making the BST can >>> be stopped when the first repeating element is caught. BUT, this will be >>> O(n) space, as the number of nodes in BST will be n-1 in worst case. >>> >>> On 19 August 2011 07:59, *$* <gopi.komand...@gmail.com> wrote: >>> >>>> only once >>>> >>>> >>>> On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh <saurab...@gmail.com>wrote: >>>> >>>>> The element is repeated only once or can be repeated k number of >>>>> times?? >>>>> >>>>> On Fri, Aug 19, 2011 at 7:50 AM, *$* <gopi.komand...@gmail.com> wrote: >>>>> >>>>>> I think we are using hash , which is like extra spaace , but as per >>>>>> the question , O(s) = 1. >>>>>> >>>>>> Thx, >>>>>> --Gopi >>>>>> >>>>>> >>>>>> On Fri, Aug 19, 2011 at 2:15 AM, icy` <vipe...@gmail.com> wrote: >>>>>> >>>>>>> #!/usr/bin/ruby -w >>>>>>> #array of unsorted positive integers >>>>>>> # find the [only] one that is duplicated >>>>>>> >>>>>>> arr= [97,2,54,26,67,12,1,19,44,4,29,36,67,14,93,22,39,89] >>>>>>> h = Hash.new(0) >>>>>>> >>>>>>> arr.each {|n| >>>>>>> h[n]+=1 >>>>>>> (puts n; break) if h[n]==2 >>>>>>> } >>>>>>> >>>>>>> #output >>>>>>> #67 >>>>>>> >>>>>>> I hope this meets the requirements ;P >>>>>>> >>>>>>> On Aug 18, 3:15 pm, "*$*" <gopi.komand...@gmail.com> wrote: >>>>>>> > How to find duplicate element (only one element is repeated) from >>>>>>> an array >>>>>>> > of unsorted positive integers.. >>>>>>> > time complexity .. O(n) >>>>>>> > space .. o(1). >>>>>>> >>>>>>> -- >>>>>>> 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. >>>>>>> >>>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> Thx, >>>>>> --Gopi >>>>>> >>>>>> >>>>>> -- >>>>>> 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. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> Saurabh Singh >>>>> B.Tech (Computer Science) >>>>> MNNIT ALLAHABAD >>>>> >>>>> >>>>> -- >>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> Thx, >>>> --Gopi >>>> >>>> -- >>>> 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. >>>> >>> >>> >>> >>> -- >>> >>> ___________________________________________________________________________________________________________ >>> >>> Please do not print this e-mail until urgent requirement. Go Green!! >>> Save Papers <=> Save Trees >>> >>> -- >>> 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. >>> >> >> >> >> -- >> Thx, >> --Gopi >> >> -- >> 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. >> > > > > -- > *Dheeraj Sharma* > Comp Engg. > NIT Kurukshetra > +91 8950264227 > > -- > 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. > -- Thx, --Gopi -- 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.
