Find duplicates in a array of elements.You are given an array of elements. some/all of them are duplicates. Find them in O(n) time and O(1) space. Property of inputs - Number are in the range of 1..n where n is the limit of the array.

Question

anonymous · Answer

@infinity_ 
@ktobah

barrycarter · Answer

Can you use hashes?

anonymous · Answer

hashes need memory

anonymous · Answer

non constant memory *

anonymous · Answer

http://stackoverflow.com/questions/4373588/find-duplicates

anonymous · Answer

I don't think that you can do that with constant memory, i think you need an array.

anonymous · Answer

may be this will work how about traversing the array
and if i get a number say 2 i copy the element in a temp and multiply 2 with the size of array nd  place it in array[2] and move the value in temp to a[0] now if u get a number greater than n its a duplicate.....

anonymous · Answer

you can't have arrays at all...

anonymous · Answer

y?

anonymous · Answer

because you say constant space.Which means that the memory used does not depent on the input.When you have an array of N elements it is O(N) space.

anonymous · Answer

yea here temp is the only space we use nd we are given that  array

anonymous · Answer

If i understand, that would work if your array was sorted...

anonymous · Answer

@infinity_ can u plz check this out? http://inder-gnu.blogspot.in/2010/11/find-duplicates-in-array-of-elements.html

anonymous · Answer

ok, do this... I would do that in O(N) space if i had to, but this is ok i guess :P

anonymous · Answer

can u xplain me what they did?