Find Missing Element In Array

How to find out a missing element in a sequence of elements, if the elements are stored in an array.

Find Single Missing Element in Sorted Array

First method is a sum of first n natural numbers, which is n(n + 1) / 2.
In our example the total should be 12 * (13) / 2 = 78
If the total (in the sum of array function) is not 78, if it is less, then how much less it is?

Suppose we have this array:

| 1 | 2 | 3 | 4 | 5 | 6 | 8 | 9 | 10 | 11 | 12 |
  0   1   2   3   4   5   6   7    8    9   10

Sum of array function:

int sum = 0;
int size = 11;
  
for (int i = 0; i < size; i++) {
  sum = sum + A[i];
}

int n = 12;
S = n * (n + 1) / 2;
S - sum; // 78 - 71 = 7;

Second method is to have the low element in the array, the high element and the size of the array. Take the element in the array, and subtract it with the index. If the difference changes at some point, then we know where is the missing element.
If we are sure that there is only one missing element, then we can stop here. If there are multiple missing ones, then we can continue till the end.

Suppose we have this array:

| 6 | 7 | 8 | 9 | 10 | 11 | 13 | 14 | 15 | 16 | 17 |
  0   1   2   3    4    5    6    7    8    9   10

int low = 6;
int high = 17;
int size = 11;

int diff = low - 0;
for (int i = 0; i < size, i++) {
  if (A[i] - i != diff) {
    printf("missing element\n", i + diff);
    break;
  }
}

Find Multiple Missing Elements in Sorted Array

Suppose we have this array:

| 6 | 7 | 8 | 9 | 11 | 12 | 15 | 16 | 17 | 18 | 19 |
  0   1   2   3    4    5    6    7    8    9   10

Since there might be more than one missing element consecutively, we have to write a loop to increment the "diff" variable.

int low = 6;
int high = 19;
int size = 11;

int diff = low - 0;
for (int i = 0; i < size; i++) {
  if (A[i] - i != diff) {
    while(diff < A[i] - i) {
      printf("%d\n", i + diff);
      diff++;
    }
  }
}

Missing Elements in Unsorted Array

| 3 | 7 | 4 | 9 | 12 | 6 | 1 | 11 | 2 | 10 |
  0   1   2   3    4   5   6    7   8    9

First, create an array that is the same size as the biggest number of the array. Initialize the array with zeros.

| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
  0   1   2   3   4   5   6   7   8   9   10  11  12

Scan through the array one by one, and increment at the corresponding index. The missing elements will still have zeros.

| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
  0   1   2   3   4   5   6   7   8   9   10  11  12

This is a simple implementation of a hash table / bitset, since we are storing to the same index and accessing it. Usually for searching algorithms, can apply hashing if possible.
One important thing about hashing, when using an array to store the elements: you need an array space equal to the largest element.


int H[12] = {0};

int starting_index = 1;
int ending_index = 12;
int num_elems = 10;

for (int i = 0; i < num_elems; i++) {
  H[A[i]]++;
}

for (int i = starting_index; i <= ending_index; i++) {
  if (H[i] == 0)
    // Missing element
    printf("%d\n", i);
}

Debugging Grimoire

Find Missing Element In Array