presc
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
#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.
*/
C
INFO