Finding Missing Elements

Methods to find one or more missing elements in an array.

Single Element Missing :

void findMissing(int a[], int n, int start) {
​
int difference = start - 0;
for (int i = 0; i < n; i++) {
if (a[i] - i != difference) {
printf("Missing Element : %d\n", i + difference);
break;
}
}
​
}

Multiple Elements Missing :

void findMissing(int a[], int n, int start) {
​
int diff = start - 0;
printf("Missing Elements :\n");
for (int i = 0; i < n; i++) {
if (a[i] - i != diff) {
while (diff < a[i] - i) {
printf("%d\t", i + diff);
diff++;
}
}
}
​
}

Using Hash Array :

void findMissing(int a[], int n, int high) {
​
// Creating and initializing hash array with 0
// Size of hash array = maximum element in input array
int h[high];
for (int i = 0; i < high; i++) {
h[i] = 0;
}
// Incrementing hash table values as per the numbers in
// original input array
for (int i = 0; i < n; i++) {
h[a[i]]++;
}
printf("Missing Elements :\n");
for (int i = low; i <= high; i++) {
if (h[i] == 0) {
printf("%d\t", i);
}
}
​
}
Contributed by Nitin Ranganath