CODEWITHSUNDEEP
c
Slav3k
Slav3k

Reputation: 37

Test task in C - my solution allegedly does not pass through some test cases

Currently I am trying to practise my c skills on some demo test tasks. I encountered following task and I implemented a solution, which does not pass the test. Can you review my solution and point out what corner cases have I missed alternatively how could I make the solution more efficient? Basically any input is appreciated!

Task:

Write a function:

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].

My solution:

int solution(int A[], int N) {
 int B[N];
    unsigned int Bidx=0;
    unsigned int i = 0;
    int smallest = 1000000;
    
    // ged rid of negative elements and find smallest positive element
    for(i=0; i<N; i++)
    {
        if(A[i]>0)
        {
            B[Bidx]=A[i];
            Bidx++;
            if(A[i] < smallest)
                smallest = A[i];
        }
    }

    // if no positive elements found, solution is 1
    if(Bidx == 0)
        return 1;

    // iterate through the positive values to find the smallest not present value
    int condition = 1;
    int candidate = smallest+1;

    while(condition)
    {
        condition = 0;

        for(i=0; i < Bidx; i++)
        {
            if(B[i] == candidate)
            {
                candidate++;
                condition = 1;
            }
        }
    }    

    return candidate;
}

Upvotes: 0

Views: 138

Answers (2)

Barmar
Barmar

Reputation: 780869

Use an array of flags exists. For each positive number n in A, set exists[n] to 1. Then find the first 0 value in exists.

#define MAXNUM 1000000

int solution(int A[], unsigned N) {
    int exists[MAXNUM + 1] = {0};
    found_positive = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] > 0) {
            found_positive = 1;
            exists[i] = 1;
        }
    }
    if (!found_positive) {
        return 1;
    }
    for (int i = 1; i <= MAXNUM; i++) {
        if (!exists[i]) {
            return i;
        }
    }
    return MAXNUM + 1;
}

Upvotes: 1

0___________
0___________

Reputation: 67476

As your integers are limited to 1e6 then a naive lookup table will be most efficient.

int solution(int A[], int N)
{
    char num[1000*1000] = {0,};

    while(N--) 
    {
        if(*A > 0) num[*A - 1] = 1;
        A++;
    }
    char *res = memchr(num, 0, 1000*1000);
    return res ? 1 + res - num : -1;
}

Instead of char as an element of the array, you can use bits which will reduce the lookup table size 8 times.

Upvotes: 1

Related Questions