1

DISCLAIMER: This is NOT a homework and neither I'm asking you to provide working code for this question.

Hi folks, I'm studying a problem with a particular property that allows to solve it in linear time with O(1) additional memory.

Here is the problem:

Given an array "A" of size N with elements ranging from 1 to N, find the duplicated element in linear time with constant space of additional memory.

In case of more than one duplicated pair, return the one that the second element has the lower index.

If there are no duplicates, return -1.

Examples:

  • A = [1, 2, 3, 4] --> -1
  • A = [1, 1, 3] --> 1
  • A = [3, 3, 1, 1, 5] --> 1

This problem is very easy to solve using a map and counting frequencies, but I'm curious about using only O(1) of extra memory...

I know that the sum of 1 + 2 + 3 + ... + N = (N*(N + 1)) / 2 and this fact may help with this problem but I really can't see how can I do better than my existing solution.

If anyone could shed some light on this for me, it would be awesome!

Jeanderson Candido
  • 364
  • 2
  • 16
  • 2
    There is a well known problem of finding a single duplicate if the elements range from 1 to N-1, for example [this answer](https://stackoverflow.com/questions/7117388/finding-out-the-duplicate-element-in-an-array?rq=1). I wonder if one of these techniques can be extended? If you are allowed to modify the array, instead look at [these answers](https://stackoverflow.com/questions/5739024/finding-duplicates-in-on-time-and-o1-space) – Peter de Rivaz Jul 30 '17 at 20:49
  • many thanks for the link! I wasn't aware of similar questions here on SO. sorry for the duplicate! thank you very much! I certainly learned something with the provided links :-) – Jeanderson Candido Jul 31 '17 at 14:48

0 Answers0