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:
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