Want to know vulnerabilities in below program finding minimum positive number greater than 0 that doesn't occur in array Below program find a minimum positive number that is greater than 0, it doesn't occur in the array. My solution actually works fulfil performance-wise. However, Codelity has given 55% only, I m trying to understand what is the potential issues with below code?



For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.



#include &lt;stdio.h&gt;

#define ARRAY_SIZE(a) sizeof(a) / sizeof(a[0])

int solution(int A[], int N) {
    // write your code in C99 (gcc 6.2.0)
    int i=0, j=0, k=0;
    int result = 1, tmp = 0;

    for(i=0; i &lt; N; i++) {
        for(j=i+1; j &lt; N; j++) {
            if(A[j] &lt; A[i]) {
                tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
            }
        }
    }

    for (i = 0; i &lt; N; i++) {
        printf("%d\n", A[i]);
    }

    for ( k = 0; k &lt; N; k++) {
        if (A[k] == result)
            result += 1;
        if (A[k] &gt; result)
            break;
    }

    return result;
}

int main(void) {
    int a[] = {1,3,6,4,1,2};
    int ret = solution(a, ARRAY_SIZE(a));
    printf("Smallest positive integer: %d\n", ret);
    return 0;
}
At first glance, your code looks quite verbose. Seeing as it was an assignment for some type of class, I'm also assuming that points would've been deducted for you doing something that is considered bad practice. With this in mind, let's go through the code:

    int i=0, j=0, k=0;
    int result = 1, tmp = 0;

    for(i=0; i &lt; N; i++) {
        for(j=i+1; j &lt; N; j++) {
            if(A[j] &lt; A[i]) {
                tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
            }
        }
    }

    for (i = 0; i &lt; N; i++) {
        printf("%d\n", A[i]);
    }


In C99, declaring all variables at the start of the function isn't required. Variables like i, j, and k should be block scoped.

You're also sorting your array in a function that is called solution. The name isn't very descriptive, and given how that function returns an integer, I wouldn't expect it to actually change the array I'm passing.

Your solution function has a single point of return. That's fine, if that's what you were asked to do. However, generally speaking, most people prefer to return early. It simplifies the code, and reduces the total number of else's quite a lot.

You're missing some checks. An array, once passed to a function, decays into a pointer. I'd write the function as int solution(int *in, int size), and if I wanted to be paranoid about safety, I'd check for in == NULL and make sure size is non-negative. Then again, the size of the array is obtained through the sizeof operator, which actually yields a value of type size_t. Perhaps it makes sense to change your function argument to accept a size_t instead of an int? size_t is unsigned, so no need to check for negative values there...

You're sorting the array in ascending order. Understandable, of course, but why aren't you using qsort? It's better practice to write functions that only do 1 thing. Your solution function handles sorting, prints some debug output, and then sets about searching the lowest missing positive integer. Let's assume, for now, that changing the array that's being passed is not an issue, I'd break things up into 2 functions and write this:

static
int sort_ascending(const void *a, const void *b) {
    int av = *(int *)a, bv = *(int *)b;

    if (av == bv)
        return 0;
    if (av &gt; bv)
        return 1;
    return -1;
}

static
int get_missing(int *in, size_t size) {
    // let's make sure the pointer can be dereferenced:
    if (in == NULL)
        return -1; // -1 is a common error value to return
    // first, sort the array
    qsort(in, size, sizeof *in, sort_ascending);

    // now let's just iterate over the array and find the answer
    // note, we're iterating until the NEXT TO LAST element, because we access in[i+1] in the body
    for (int i = 0; i &lt; size-1; i++) {
        int v = in[i]+1; // the lowest possible value based on in[i]
        // if v is positive, and smaller than the next value in the array
        // we're done, and we can return
        if (v &gt; 0 &amp;&amp; v &lt; in[i+1])
            return v;
    }
    // we didn't return from the loop. The lowest value is in[size-1]+1, if it's positive:
    int last = in[size-1]+1;
    if (last &gt; 0)
        return last;
    // the highest value in the array was still negative, so the lowest positive missing value is 1
    return 1;
}


The last bit (getting the last value from the input, adding 1 and returning) is something that I'd probably leave at the end, but some might choose to perform this check before iterating the array. If the last (highest) value in the array is still negative, the loop is just a waste of time. The function then would look like this:

static
int get_missing(int *int, size_t size) {
    if (in == NULL || size == 0)
        return -1;
    qsort(in, size, sizeof *in, sort_ascending);

    if (in[size-1] &lt;= 0) // highest value is 0 or less
        return 1;

    for (int i = 0; i &lt; size -1; i++) {
        int v = in[i]+1;
        if (v &gt; 0 &amp;&amp; v &lt; in[i+1])
            return v;
    }
}


As you can see, the function is a lot smaller, and fairly easy to read. The thing I don't like about checking the last element in the array before iterating is that it means the last return in the function is kind of "hidden" in a loop body. That may be personal preference, and if the input array is potentially huge, it's likely to be more efficient to preform that check. Then again, using qsort_r and passing in a pointer to an int allows you to count the number of negative values in the array, and that way you can start the iteration at the correct offset right away, but that's premature optimization. Let's get back to the matter at hand.



What was changed:

So far, we've changed:


Sorting separated out in a separate function, and using qsort rather than a nested loop
Checking for zero and NULL array
Returning early
Have error values returned in case the input is invalid (a -1)


What we still haven't addressed is the side-effect your function has. The input array is altered. This is considered bad practice (unless it's well documented, and is done for a clear reason). The way I'd solve it is by creating a copy:

static
int get_missing(const int *in, size_t size) {
    if (in == NULL || size == 0)
       return -1;
    // allocate memory for copy of input array
    int *temp = malloc(size * sizeof *in);
    if (temp == NULL)
        return -1;
    // copy the array
    memcpy(temp, in, size * sizeof *temp);

    // from here on, we use the copy
    qsort(temp, size, sizeof *temp, sort_ascending);
    if (temp[size-1] &lt;= 0) {
        free(temp); // free memory
        return 1;
    }

    for (int i = 0; i &lt; size -1; i++) {
        int v = temp[i]+1;
        if (v &gt; 0 &amp;&amp; v &lt; temp[i+1]) {
            free(temp);
            return v;
        }
    }
}


Now if we do something like:

int main( void ) {
    int arr[] = int a[] = {1,3,6,4,1,2};
    int ret = get_missing(arr, ARRAY_SIZE(arr));
    for (int i=0; i &lt; ARRAY_SIZE(arr); i++)
        printf("arr[%d] = %d\n", i, arr[i]);
    printf("Lowest positive int not in arr is %d\n", ret);
    return 0;
}


You'll see that the original array was not altered. The get_missing function now also communicates that clearly to:

int get_missing(const int *in, size_t size);


Looking at this, I know right away this function will return an int, accepts a pointer (decayed array), and will not change the argument (as it's const). I am expected to pass in a size value, which cannot be negative.

Putting it all together:

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;

#define ARRAY_SIZE(a) (sizeof(a) / sizeof(a[0]))

static
int sort_callback(const void* a, const void* b) {
    int av = *((int *)a), bv = *(int *)b;

    if (av == bv)
        return 0;
    if (av &lt; bv)
        return -1;
    return 1;
}

static
int get_missing_sideeffect(int *arr, int size) {
    qsort(arr, size, sizeof *arr, sort_callback);

    for (int i = 0; i &lt; size-1; i++) {
        int next = arr[i] +1;
        if (next &gt; 0 &amp;&amp; arr[i+1] &gt; next)
            return next;
    }

    int last = arr[size-1];
    if (last &lt;= 0)
        last = 0;

    return last+1;
}

static
int get_missing(const int *in, size_t size) {
    if (in == NULL || size == 0)
       return -1;

    int *temp = malloc(size * sizeof *in);
    if (temp == NULL)
        return -1;

    memcpy(temp, in, size * sizeof *in);

    qsort(temp, size, sizeof *temp, sort_callback);
    if (temp[size-1] &lt;= 0) {
        free(temp);
        return 1;
    }

    for (int i = 0; i &lt; size -1; i++) {
        int v = temp[i]+1;
        if (v &gt; 0 &amp;&amp; v &lt; temp[i+1]) {
            free(temp);
            return v;
        }
    }
}

int main(void) {
    int a[] = {1,3,6,4,1,2};
    int ret1 = get_missing(a, ARRAY_SIZE(a));
    // prints out a unchanged
    for (int i = 0; i &lt; ARRAY_SIZE(a); i++)
        printf("a[%d] = %d\n", i, a[i]);
    int ret2 = get_missing_sideeffect(a, ARRAY_SIZE(a));

    printf("Smallest positive integer: %d -&gt; %d\n", ret1, ret2);

    // shows a was changed due to side-effect
    for (int i = 0; i &lt; ARRAY_SIZE(a); i++)
        printf("a[%d] = %d\n", i, a[i]);

    return 0;
}




As chux correctly pointed out: the version I posted here could've resulted in integer overflow. To fix this problem, it's a simple matter of returning 0 to indicate an error, and an unsigned int in all other cases (if the input has all ints up to (and including) INT_MAX).

Another issue I've realised is that the code wouldn't return a value like 1, if the input looked something like {2, 3, 4, 5}, whereas clearly, the smallest positive int missing from the array is 1. For these reasons, I'll write a final version of get_missing here:

static
unsigned int get_missing(const int *in, size_t size) {
    if (in == NULL || size == 0)
       return 0;

    int *temp = malloc(size * sizeof *in);
    if (temp == NULL)
        return 0;

    memcpy(temp, in, size * sizeof *in);

    qsort(temp, size, sizeof *temp, sort_callback);

    // lowest value in temp &gt; 1, or highest value is zero or less
    if (temp[0] &gt; 1 || temp[size-1] &lt;= 0) {
        free(temp);
        return 1;
    }

    unsigned int v = 0;
    for (int i = 0; i &lt; size -1; i++) {
        v = temp[i]+1u;
        if (v &gt; 0 &amp;&amp; v &lt; temp[i+1]) {
            free(temp);
            return v;
        }
    }
    return v;
}


So I've added the check to make sure we return 1 if the input starts with 2 or more. I've changed the function to return an unsigned int (which means you have to print the output using printf("Return value %ud\n", ret);). Lastly, I'm also declaring v outside of the for loop. The last return statement won't ever be reached, but when I compiled the code in its original form (gcc -std=c99 main.c -o missing -Wall), the compiler spits out a warning.