Codility – Demo Tast – MissingInteger

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 =&gt; x).ToArray();

var max = A.Max();
var min = A.Min();

if (min &gt; 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

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