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.
