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(log(N)) memory complexity.
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?