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;
}
Nice brief and this fill someone in on helped me alot in my college assignement. Thank you as your information.
Nice post. Keep up the great work
Hey nice one…. it helped me.
The above solution was correct but looked crazy.
Here is my solution:
#include
#include
#include
#include
using namespace std;
int const MAX = 100;
void findDupMissElement(int a[], int len, int &dup, int &missing)
{
map count;
for (int i = 0; i < len; ++i) {
count[a[i]]++;
}
for (int i = 0; i < len; ++i) {
if (count[a[i]] == 2) {
dup = a[i];
}
if (count[i] == 0) {
missing = i;
}
}
}
int main()
{
int arr[MAX];
srand(time(NULL));
int missing = rand() % MAX;
int dup = rand() % MAX;
for (int i = 0; i < MAX; ++i) {
if (i == missing) {
arr[i] = dup;
} else {
arr[i] = i;
}
}
for (int i = 0; i < MAX; ++i) {
cout << arr[i] << ", ";
}
cout << endl;
dup = missing = -1;
findDupMissElement(arr, MAX, dup, missing);
cout << "Duplicate number: " << dup << endl;
cout << "Missing element: " << missing << endl;
}