MissingInteger

Find the smallest positive integer that does not occur in a given sequence
ℹ️ © Codility, 2009-2018

Problem

This is a demo task.

Write a function 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.

Assume that:
• 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].

Complexity:
• expected worst-case time complexity is O(n);
• expected worst-case space complexity is O(n) (not counting the storage required for input arguments).

Solution

C#

using System;
class Solution {
  public int solution(int[] A) {
    if (!Array.Exists(A, a => a == 1)) {
      return 1;
    }
    A = A.Where(a => a > 0).ToArray();
    Array.Sort(A);
    int n = A.Length;
    for (int i = 1; i < n; i++) {
      if (A[i] - A[i - 1] > 1) {
        return A[i - 1] + 1;
      }
    }
  return A[n - 1] + 1;
  }
}

Java

import java.util.Arrays;
class Solution {
  public int solution(int[] A) {
    ⚠️
  }
}

JavaScript

function solution(A) {
  let s = new Set(A);
  let n = 1;
  while (s.has(n)) {
    n++;
  }
  return n;
}

PHP

function solution($A) {
  if (!in_array(1, $A)) {
    return 1;
  }
  $A = array_filter($A, function ($a) {
    return $a > 0;
  });
  sort($A);
  $n = count($A);
  for ($i = 1; $i < $n; $i++) {
    if ($A[$i] - $A[$i - 1] > 1) {
      return $A[$i - 1] + 1;
    }
  }
  return $A[$n - 1] + 1;
}