Find the Duplicate
October 13th, 2007Dany Valevsky gave me this very cool riddle.
You are given a vector of size N, the elements of which are numbers in the range 1,…,N-1. I.e. there is at least one repeating element. Give an algorithm that finds a repeating element (it does not matter which one, in case there are several) with O(N) time complexity and O(1) memory complexity.
NOTE - the time and memory complexities are calculated in integers. I.e. the input is of size N, not N*logN.
That’s it!
Pages: 1 2
October 14th, 2007 at 3:12 pm
I know of a solution, but I’ll withhold it for the time being. Just want to make a clarification: I think you mean O(1) memory complexity. At least, that’s the way I know the riddle.
October 14th, 2007 at 4:19 pm
No, I did mean O(log(N)). Just to read the values from the buffer you need O(log(N)) memory (the size of the pointer!).
October 14th, 2007 at 4:20 pm
Dan,
PS – you are welcome to post your solution on the second page.
October 31st, 2007 at 10:35 pm
good one!
p.s
I couldn’t find the porn, is it in your previous posts?
August 31st, 2010 at 8:39 pm
A clarification – the solution takes O(log(N)) bits of memory and O(N * logN) time, if you are only allowed actions on bits. Note that in this case the size of the input is N*log(N).
It is simpler to count the complexity in integers, in which case it is indeed O(N) running time and O(1) memory.