Codility – Demo Tast – MissingInteger

Task description

Write a function:

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

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

Solution in C#:

using System;
using System.Collections.Generic;
using System.Linq;

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

        var result = -1;        
        A = A.OrderBy(x => x).ToArray();
        
        var max = A.Max();
        var min = A.Min();
        
        if (min > 1) return 1;
        if (A.Length == 2 &amp;&amp; min < 0 &amp;&amp; max &gt; 1) return 1;
        
        for (int i = 0; i < A.Length-1;  i++) {
            if (A[i] < 0) continue;
            if (A[i+1]-A[i] &gt; 1){
                result = A[i]+1;
                break;
            }
        }
        
        if (result == -1)
            if (max <= 0) result = 1;
            else if(min &gt; 1) result = 1;
            else result = max+1;

        return result;
    }
}

Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.