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 <[email protected]> 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, *$* <[email protected]> wrote: > >> only once >> >> >> On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh <[email protected]>wrote: >> >>> The element is repeated only once or can be repeated k number of times?? >>> >>> On Fri, Aug 19, 2011 at 7:50 AM, *$* <[email protected]> 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` <[email protected]> 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, "*$*" <[email protected]> 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 [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> 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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
