We need to find the first repeating element in an unsorted array without using any auxiliary storage.
from the array { 1 2 3 4 5 4 2 3}
we return op = 4 (first repeated number)
If the elements are in the range 1-n, and the array has length n, then you can mark positions in the array. For example, you could flip the sign to denote that a number has occurred before.
for i = 1 to N
{
if(arr[arr[i]] is negative)
return arr[i];
else
arr[arr[i]] *= (-1);
}
return No_duplicates;
Read full article from First Repeated Number. | techpuzzl
from the array { 1 2 3 4 5 4 2 3}
we return op = 4 (first repeated number)
If the elements are in the range 1-n, and the array has length n, then you can mark positions in the array. For example, you could flip the sign to denote that a number has occurred before.
for i = 1 to N
{
if(arr[arr[i]] is negative)
return arr[i];
else
arr[arr[i]] *= (-1);
}
return No_duplicates;
Read full article from First Repeated Number. | techpuzzl
