Saturday, October 1, 2011

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

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;
}


0 comments:

Post a Comment