Find the missing integer in Codility

algorithm, c#

Solution

Edit: Added detail to answer your actual question more directly.

"Please help me out, where I am wrong."

In terms of correctness: Consider `A = {7,2,5,6,3}`. The correct output, given the contents of `A`, is `1`, but our algorithm would fail to detect this since A.Min() would return `2` and we would start looping from `3` onward. In this case, we would return `4` instead; since it's the next missing value.

Same goes for something like `A = {14,15,13}`. The minimal missing positive integer here is again `1` and, since all the values from 13-15 are present, the `value` variable will retain its initial value of `value=A[0]` which would be `14`.

In terms of performance: Consider what `A.Min()`, `A.Max()` and `A.Contains()` are doing behind the scenes; each one of these is looping through `A` in its entirety and in the case of `Contains`, we are calling it repeatedly for every value between the `Min()` and the lowest positive integer we can find. This will take us far beyond the specified `O(N)` performance that Codility is looking for.

By contrast, here's the simplest version I can think of that should score 100% on Codility. Notice that we only loop through `A` once and that we take advantage of a `Dictionary` which lets us use `ContainsKey`; a much faster method that does not require looping through the whole collection to find a value.

using System;
using System.Collections.Generic;

class Solution {
    public int solution(int[] A) {

        // the minimum possible answer is 1
        int result = 1; 
        // let's keep track of what we find
        Dictionary<int,bool> found = new Dictionary<int,bool>();

        // loop through the given array  
        for(int i=0;i<A.Length;i++) {
            // if we have a positive integer that we haven't found before
            if(A[i] > 0 && !found.ContainsKey(A[i])) {
                // record the fact that we found it
                found.Add(A[i], true);
            }
        }

        // crawl through what we found starting at 1
        while(found.ContainsKey(result)) {
            // look for the next number
            result++;
        }

        // return the smallest positive number that we couldn't find.
        return result;
    }
}

Problem

``` I need to "Find the minimal positive integer not occurring in a given sequence. " A[0] = 1 A[1] = 3 A[2] = 6 A[3] = 4 A[4] = 1 A[5] = 2, the function should return 5. Assume that: N is an integer within the range [1..100,000]; each element of array A is an integer within the range [−2,147,483,648..2,147,483,647]. ``` I wrote the code in codility, but for many cases it did not worked and the performance test gives 0 %. Please help me out, where I am wrong. ``` class Solution { public int solution(int[] A) { if(A.Length ==0) return -1; int value = A[0]; int min = A.Min(); int max = A.Max(); for (int j = min+1; j < max; j++) { if (!A.Contains(j)) { value = j; if(value > 0) { break; } } } if(value > 0) { return value; } else return 1; } } ``` The codility gives error with all except the example, positive and negative only values.

Original source

Related problems