Understanding the concept behind finding the duplicates in an array

Question

I found a method to find the duplicates in an array of n elements ranging from 0 to n-1.

Traverse the array. Do following for every index i of A[].
{
    check for sign of A[abs(A[i])] ;
    if positive then        
      make it negative by   A[abs(A[i])] = -A[abs(A[i])];
    else  // i.e., A[abs(A[i])] is negative
      this element (ith element of list) is a repetition
}

This method works fine. But I fail to understand how. Can someone explain it?

I am basically looking for a proof or a simpler understanding of this algorithm!

Answer 1

You're basically cheating by using the sign bits of each array element as an array of one-bit flags indicating the presence or absence of an element. This might or might not be faster than simply using a separate bit-set array, but it certainly makes use of the special case that you are using a signed representation (int) of unsigned values, therefore you have an extra unused bit to play with on each. This would not work if your values were signed, for example.