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(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

8 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?

  5. yaniv Says:

    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.

Leave a Reply