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.
