Interview Questions #6

/*
 *int solution(int A[], int N);
 *
 *that, given an array A of N integers, returns the smallest positive integer 
 *(greater than 0) that does not occur in A.
 *
 *For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
 *
 *Given A = [1, 2, 3], the function should return 4.
 *
 *Given A = [−1, −3], the function should return 1.
 *
 *Write an efficient algorithm for the following assumptions:
 *
 *N is an integer within the range [1..100,000];
 *each element of array A is an integer within the range [−1,000,000..1,000,000].
 */


#include <stdio.h>
int solution(int A[], int N) {
    // write your code in C99 (gcc 6.2.0)
    int i, smallest = 1;
    for (i = 0; i < N; i++) {
        // Only positive integers come here
        if ((A[i] > 0) && (smallest == A[i])) {
            smallest++;
            i = -1;
        } 
    }
    return smallest;
}

int main()
{
   int A[] = {-1, -3};
   int result = 0;
   int N = sizeof(A)/sizeof(A[0]);
   result = solution(A, N);
   printf("The smallest positive integer is %d in the given array", result);
   return 0;
}

Output:

The smallest positive integer is 1 in the given array