Find the Duplicate

Rating: 4
October 13th, 2007

Dany 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

7 Responses to “Find the Duplicate”

  1. Dan Says:

    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.

  2. yaniv Says:

    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!).

  3. yaniv Says:

    Dan,

    PS - you are welcome to post your solution on the second page.

  4. david Says:

    good one!

    p.s
    I couldn’t find the porn, is it in your previous posts?

Leave a Reply