presc

#include <stdio.h>
 
/*
 * Given a series of positive sequential numbers (incremented by 1), find the first missing number.
 */

/*
 GetMissingNumber takes array and size of array as arguments
 */
// one approach
int GetMissingNumber1 (int a[], int n)
{
    int i, total;
    total  = (n+1)*(n+2)/2;   
    for ( i = 0; i< n; i++)
       total -= a[i];
    return total;
}

// another approach
int GetMissingNumber2 (int a[], int n)
{
    int i, num = a[0];
    for (i=0; i<n; i++) {
        if (num == a[i]) {
            num++;
        } else {
            return num;
        }
    }
}

// try to write an implementation with O(log(n))
int missingNumber(int a[], int min, int max) {
    int pivot;
    
    if (min >= max)
        return min + 1;
        
    pivot = (min + max) / 2;
    if (a[pivot] == pivot + 1)
        return missingNumber(a, pivot + 1, max);
    return missingNumber(a, min, pivot);
}

int GetMissingNumber3 (int a[], int n) {
    return missingNumber(a, 0, n);
} 

/*
 * Program to test above functions
 */
int seq_main()
{
    int a[] = {1,2,4,5,6};
    int miss;
    miss = GetMissingNumber1(a,5);
    printf("%d\n", miss);
    miss = GetMissingNumber2(a,5);
    printf("%d\n", miss);
    miss = GetMissingNumber3(a,5);
    printf("%d\n", miss);
}

/*
 * Output will be 3.
 */