This is O(n) and uses two local variables. It does not fail if n>65536
as the solutions which use the sum of the elements will. And I believe
that it is simpler and more understandable. It pigeonholes each
element until it finds one which is already in its spot, and that one
is the duplicate. Each iteration puts one element in its spot, so the
process is O(n).
int dup(int *a, int n)
{
int i,j;
for(i = 0; i < n; ++i)
{
while(a[i] != i)
{
j = a[i];
if (a[j] == j) return j;
a[i] = a[j];
a[j] = j;
}
}
return -1; // No duplicate
}
On Nov 18, 9:01 am, shady <sinv...@gmail.com> wrote:
> Given an array of size n, which has all distinct elements between 1 to n
> with one element repeating, which also implies that one element is missing.
> How to find the repeating element without using extra space and linear time
> complexity ?
>
> Any way to do it with exor ? :P
--
