Back to: Data Structures and Algorithms Tutorials

**Finding Multiple Missing Elements in a Sorted Array in C:**

In this article, I am going to discuss **Finding Multiple Missing Elements in a Sorted Array in C** Language with Examples. In our previous article, we have seen **how to find a single missing element in a sorted array**.

**How to Find Multiple Missing Elements in a Sorted Array?**

We have an array of some missing elements that we have to find:

In the above array, there are 3 elements missing which are 12, 17, 22, and 22. So here more than one element is missing and also after 20 continuously 2 elements are missing. Here also we will follow the same method which we discuss in our previous article. We will iterate all the elements of an array by checking the difference between element and index.

**1**^{st} Missing Element:

^{st}Missing Element:

The difference of 1^{st} element to the corresponding index (0) is: 11 – 0 = 11

2^{nd} element to the corresponding index (1) is 13 – 1 = 12

12 is not the same as the previous difference, which means there is a missing element. We will find that missing element by adding the difference to that corresponding index number, so, 11 is the difference and index number is 1, so by adding them we will get 12. It is our first missing element. We know that there are more missing elements, so we can’t track the whole array with the same difference. We have to modify the difference when we found any missing element. Here the new difference will 12.

**2**^{nd} Missing Element:

^{nd}Missing Element:

Now the new difference is 12. Let iterate from where we left in the array.

The difference of:

3^{rd} element to the corresponding index (2) is: 14 – 2 = 12

4^{th} element to the corresponding index (3) is 15 – 3 = 12

5^{th} element to the corresponding index (4) is: 16 – 4 = 12

6^{th} element to the corresponding index (5) is 18 – 5 = 13

Here, 12 is not the same as the previous difference, there is a missing element. So again, for finding the missing element we will repeat the step. Now, add the difference and index number. 12 is the difference and 5 is the index number, so by adding them we will get 17. So, 17 is the 2^{nd} missing element. Now the new difference is 13.

**3**^{rd} and 4^{th}Missing Elements:

^{rd}and 4

^{th}Missing Elements:

Now the new difference is 13. Let iterate from where we left in the array.

The difference of:

7^{th} element to the corresponding index (6) is 19 – 6 = 13

8^{th} element to the corresponding index (7) is: 20 – 7 = 13

9^{th} element to the corresponding index (8) is 23 – 8 = 15

Here, 15 is not the same as the previous difference, here 15 – 13 is 2 means there are two missing elements. So again, for finding the missing element we will repeat the step. Now, our difference is 13, so,

13 + 8 = 21,

Increment difference by 1 then,

14 + 8 = 22

So, 21 and 22 are our 3^{rd} and 4^{th} continuously missing elements. When the difference will greater than one, we will increment the index (current index to the new index). We can continue further but as we know there are no more missing elements in the array so we have left here. In this way, we can find multiple missing elements in a sequence of elements or an array.

**Pseudo Code:**

for (i = 0; i < n; i++){ if(C[i] - i != difference){ while(difference < C[i] - i){ printf("%d\n", i + difference); difference++; } } }

While loop is used in the above code because we have to print missing elements and increment the difference if there is a difference greater than 1.

**Full code in C language:**

#include <stdio.h> #include <stdlib.h> struct List{ int C[15]; int size; int length; }; void Display(struct List list) { int i; printf("Elements are:\n"); for (i = 0;i<list.length;i++) printf("%d ", list.C[i]); printf("\n\n"); } void MissingElements(struct List list){ int diff = list.C[0]; printf("Missing Elements are: \n"); for (int i = 0; i < list.length; i++){ if(list.C[i] - i != diff){ while(diff < list.C[i] - i){ printf("%d\n", i + diff); diff++; } } } } int main(){ struct List list_1 = {{11,13,14,15,16,18,19,20,23,24,25}, 15, 11}; Display(list_1); MissingElements(list_1); }

**Time Complexity: O (n)**

**Output:**

**Finding Multiple Missing Elements in Array Method (2**^{nd} Method):

^{nd}Method):

Now, we will see another method to find out multiple missing elements or sequences of elements in an array (2^{nd} Method). This method is the faster method as compared to the previous method. So below is an example of array ‘C’ which has the lowest element: 1, highest element: 12, and size are 10:

By noticing the above array, there are all numbers present from 1 to 12 but 5 and 8 are missing. Our previous method takes O (n) time with some extra time for increment difference variable but there we neglect this time as it was too small. But this method takes O (n) time without any extra time.

For making this method faster, we have taken an extra array which index is from 0 to 12. In this method, we will take the size of the second array as the largest element present in the given array. Here, 12 is the max number so we have taken an extra array of size 12:

We have initialized the extra array with 0. Why do we initialize with 0? Let’s have a look at the procedure:

We have to scan through the array one by one element.

**1**^{st} Element:

^{st}Element:

In the given array, 1^{st} element is **3.** Now, go to the **3 ^{rd}** index of the extra array and increment the value of the 3

^{rd}index:

**2**^{nd} Element:

^{nd}Element:

Now the next is the 2^{nd} element which is 7. Now, go to the 7^{th} index of the extra array and increment the value of the 7^{th} index:

**3**^{rd} Element:

^{rd}Element:

Now the next is 3^{rd} element which is 4. Now, go to the 4^{th} index of the extra array and increment the value of the 4^{th} index:

In this way, we have traced the whole array and modified the extra array as:

So, what do we do? We just increment that particular index that is present in the given array. So zero are that indices that are not present in the given array and one is those indices that are present in our array. Now our extra array has 3 indexes of zero elements which are: 0, 5, and 8. Here we will neglect zero because it is not present in the given array as our array start from 1. Still, there are two places that are zero. So, these two elements are missing.

Now we will scan the extra array and print only those elements which have the value of zero. This is a simple and faster procedure. As we just scanned the list of elements and increment the indices of the extra array. So, for incrementing the value it just takes constant time and for scanning, it will take n time, so,

**Time Complexity: O (n)**

Here we named our extra array ‘H’ and it is known as Hash Table. We will discuss the hash table later in our upcoming articles. But here we did a simple implementation of hast table. As we scan the array one by one element, we just go to the same index and increment it.

Always remember hast table takes constant time. That is the ideal time for hashing is constant. We can also call it a bitset. Here we haven’t implemented the complete mechanism of hashing technique like using a hash function and other things. But it is the simplest form of hashing. Here, we need an array space equal to the largest element. So extra array can take a lot of space. So, space, if it is a constraint then you cannot use this hashing (if you have limited space).

But the machines that we are using have abandoned the memory space, so we hardly bother about memory space. So hashing is the best solution.

**Full Code in C language:**

#include <stdio.h> #include <stdlib.h> struct List{ int C[15]; int size; int length; }; void Display(struct List list) { int i; printf("Elements are:\n"); for (i = 0;i<list.length;i++) printf("%d ", list.C[i]); printf("\n\n"); } void MissingElements_2(struct List list, int low, int high, int size){ int H[size]; for(int i = 0; i < size; i++){ H[i] = 0; } for(int i = 0; i < list.length; i++){ H[list.C[i]]++; } printf("Missing Elements are: \n"); for (int i = low; i <= high; i++){ if(H[i] == 0) printf("%d\n", i); } } int main(){ struct List list_1 = {{3, 7, 4, 9, 12, 6, 1, 11, 2, 10}, 10, 10}; Display(list_1); MissingElements_2(list_1, 1, 12, 10); }

**Output:**

In the next article, I am going to discuss **Finding Duplicates in a Sorted Array in C Language** with Examples. Here, in this article, I try to explain **How to Find Multiple Missing Elements in a Sorted Array in C Language **with Examples and I hope you enjoy this Finding Multiple Missing Elements in a Sorted Array in C Language with Examples article.