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

#### by manojgumber

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

Advertisements

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;

}

ok boss you win………….your solution will take atleast 2-3 hours to understand.