**Question:**there is a size-N array of integers whose values range from 1 to N. Some integers are duplicated. Find the first duplicate and its index without using any extra memory (not even O(1)).

**Solution:**there are a few keys in the question that we should consider:

- The array size is a finite number N which is also the upper limit for any integer inside the array. Hence, if the array size is 10, then there are ten elements in the array and each of those elements is between 1 and 10.
- Some elements are just duplicates. That means the array may not contain all numbers between 1 and N.
- We need to find only the first duplicate. Thus, as soon as we discover one, we can stop.
- No extra memory is allowed, not even O(0). That means we can't use any extra storage or declare any new variable inside our algorithm because that is O(1).

We know that each element's value is between 1 and N, so if we increase that value by (N + 1), the modulus of that value and N + 1 is still the same. For example, modulus of 2 and (N + 1) is 2 and modulus of 2 + N + 1 is still 2. Thus, we can mark a visited element by adding N + 1 into its value or any element's value in the array because that doesn't change its modulus with N + 1 at all!

Furthermore, we know that each element's value is between 1 and N. Hence, we can use each element's value as a key and the element at array[key] as the mark. For example, if the current element is 4 then we can check if its value has been visited, and thus a duplicate, by looking at the value of the element at index 4 in the array, if the current element is 2 the we check the value of the element at index 2 in the array, and so on.

One final point, we need to traverse the array and check each element, so we need a loop that run till we find the duplicate or till we reach the end of the array. The problem with such loop is that it needs additional counter / sentinel value as the loop's termination condition! That requires memory allocation. Fortunately, we know that the first element is not a duplicate because there is no other element in front of it. Thus, we can use the first element in the array as our counter.

This algorithm is short but difficult to understand without doing an example, so lets take a look at the algorithm implementation and go straight to an example:

http://codesam.blogspot.com/2011/04/find-first-duplicated-integer-in-array.html

let the array be 3 1 2 1 3 4

ReplyDeletefirst repeated integer is 3 here

start from the first and go till the end

add n+1 to the a[a[i]] where i is the current index.

iterate again dividing the values by n+1 if values comes 1 . the remainder is the repeated one.