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
Now a and b the sum of 1st n numbers and square of n numbers respectively.
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.
(Because we already know a,b,S,S1)
Code:
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;
}