### One duplicate , one missing element in an array

You have an array of size 100 which stores integers from 0 to 99.
In this array one number is a duplicate, that means one is missing.

How can we find duplicate and missing ?

Method 1

1. Since one element is missing , some element must be repeated once in the array.
2. Let x be the missing and y be the repeated element
3. Calculate the sum of all the elements and sum of squares of all the elements of array.

S=Sum of all the elements of array
S1= Sum of squares of all the elements of array

Sum of first n natural numbers=a= ( n * (n+1) )/2
Sum of squares of first n natural no=b= n * (n+1) * (2n+1) / 6

a=S+x-y
b=S1+x^2- y^2

(b-S1)/(a-S)=x+y;

Now we have 2 equations and 2 variables & hence both x and y can be found.

```
int
main ()
{
int a[100];
for (int i = 0; i < 100; i++)
{
a[i] = i;
} a[45] = 33;
cout << findDuplicate (a, 100) << endl;
return 0;

}

int
findDuplicate (int array[], int size)
{
int s = 0;
int s1 = 0;

int n = size - 1;
int a = (n * (n + 1)) / 2;
int b = (n * (n + 1) * (2 * n + 1)) / 6;

for (int i = 0; i < size; i++)
{
s = s + array[i];
s1 = s1 + (array[i] * array[i]);
}

int x = ((a - s) + (b - s1) / (a - s)) / 2;
return x;
}

```