CODEWITHSUNDEEP
carraysalgorithmperformance
Mitsos101
Mitsos101

Reputation: 571

Find count of missing elements in an unsorted array of integers

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.

Upvotes: 0

Views: 1100

Answers (1)

Giorgi Moniava
Giorgi Moniava

Reputation: 28674

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.

Upvotes: 2

Related Questions