#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() 
{   
int n;
scanf("%d",&n);
int a[n],i=0;
//Reading elements
for(i=0;i<n;i++){
    scanf("%d",&a[i]);
}
int min=__INT_MAX__,max=0;
//Finding the minimun and maximum from given elements
for(i=0;i<n;i++){
    if(a[i]>max)
    max=a[i];
    if(a[i]<min)
    min=a[i];
}
int len=max-min,diff=0-min,miss;
int b[len];
//Creating a new array and assigning 0
for(i=0;i<len;i++)
    b[i]=0;
//The corresponding index value is incremented based on the given numbers
for(i=0;i<n;i++){
    b[a[i]+diff]++;
}
//Finding the missed value
for(i=0;i<len;i++){
    if(b[i]==0){
        miss=i-diff;
        break;
    }
}
printf("%d",miss);
}

Code Explanation:

1.Find the minimum and maximum in the given numbers.

2.Create an count array of size (maximum-minimum) and iniatizing to 0, which maintains the count of the given numbers.

3.Now by iterating, for each given element increment the corresponding index by 1.

4.Finally iterate through the count array and find the first missing number.

This might help you in solving your problem. Correct me if i'm wrong.

I think, it will be easy to solve sort of problems using data-structure like TreeMap in JAVA, e.g:

treeMap.put(array[i], treeMap.get(array[i]) == null ? 1 : treeMap.get(array[i]) + 1);

So, you are putting key and value to the TreeMap the key represent the digit itself e.g, 1,2,3... and the value represent the occurrence times.

Thus, and by taking advantage of this data-structure (Sort elements for us) you can loop through this data-structure and check which key is missing in the sequence, e.g:

for key in treeMap
   if(key > currentIndex) // this is the missing digit
   if(loop-completed-without-missing-key) // it's not in the array.

Add the numbers to a running array and keep them sorted.

You may also have optional minimum and maximum bounds for the array (to handle your third case, "6 is missing even if not in array"

On examination of a new number: - try inserting it in the sorting array. - already present: discard - below minimum or above maximum: nullify minimum or maximum accordingly - otherwise add in proper position.

To handle an array: sort it, compare first and last elements to expected minimum / maximum. Nullify minimum if greater than first element, nullify maximum if smaller than last element.

There might be a special case if minimum and maximum are both above first or both above last:

 min=5 max=8   array = [ 10, 11, 13 ]

 Here 5, 6, 7, 8 and 12 are missing, but what about 9? Should it be considered missing?

When checking for missing numbers include: - if minimum is not null, all numbers from minimum to first element. - if maximum is not null, all numbers from last element to maximum. - if (last - first) = number of elements, no numbers are missing (total numbers examined minus array size is duplicate count) - otherwise walk the array and report all missing numbers: when checking array[i], if array[i]-array[i-1] != 1 you have a gap.

only "first" missing

You still have to manage the whole array even if you're only interested in one missing number. For if you discarded part of the array, and the missing number arrived, then the new missing number might well have been in the discarded part of the array.

However you might keep trace of what the smallest missing number is, and recalculate with cost of o(log n) only when/if it arrives; then you'd be able to tell which is it in o(1) time. To quickly zero on that missing number, consider that there is a gap between arr[i] and arr[j] iff arr[j]-arr[i] > j-i.

So you can use the bisection method: start with i = first, j = last; if gap(i,j) then c = ceil(i+j)/2. If gap(i, c) then j = c, else i = c, and repeat until j-i = 1. At that point arr[i]+1 is your smallest missing number.