Find count of missing elements in an unsorted array of integers

Question

How can I find how many elements are missing from an array of integers in C, if some of the numbers are duplicated?

Assume the array is int array = {1, 2, 1, 5, 4} and there should be numbers up to 6. Then, the program/function should output/return 2, as there are 2 elements missing (3, 6).

Note: 0 is not counted as a missing number, nor can it be present in an array.

• YoungHobbit: Are you saying an array of length n can have numbers between 1 to n+1?
• Mitsos101: @YoungHobbit No, the array elements could've been the same, but for example numbers up to 10 could have been missing. Therefore, there would be 6 elements missing. The maximum number of the sequence (6 in the question) can be anything. (But it is obviously specified beforehand)

Answer 1

This way?

int countMissing(int *x, int arrLen, int bound)
{
 int * y = malloc ((bound + 1) * sizeof(int));
 int i = 0;
 int missing = 0;
 memset(y,0,sizeof(int)*(bound+1));
 for(i = 0; i<arrLen; i++)
 {
 if(x[i]<=bound)
 {
 y[x[i]] = 1;
 }else
 {
 // error handling e.g.
 return -1;
 }
 }
 for(i = 1; i<=bound; i++)
 {
 if(y[i]==0) missing++;
 }
 free(y);
 return missing;
}

Usage:

int main(void) 
{
 int array [] = {1, 2, 1, 5, 4};
 printf("%d", countMissing(array, 5, 10));
 return 0;
}

Output: 6.

• nneonneo: Nits: (1) you should allocate char *y to save some space; (2) you should use y[x[i]-1] or allocate an array of size bound+1, because otherwise you have an out-of-bounds access; (3) you should free your array.
• gmoniava: @nneonneo: fixing, I don't have a debugger with me; should work now
• Mitsos101: Why are you using memset() instead of calloc()?
• gmoniava: @Mitsos101: That is a style thing
• Mitsos101: @Giorgi Does the memory need to be zeroed out anyway though?