I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Find first missing positive

From Rosetta Code
Find first missing positive is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Task

Given an integer array nums   (which may or may not be sorted),   find the smallest missing positive integer.


Example
  •    nums  =   [1,2,0], [3,4,-1,1], [7,8,9,11,12]
  •   output =   3, 2, 1



APL[edit]

Works with: Dyalog APL
fmp ← ⊃(⍳1+⌈/)~⊢
Output:
      fmp¨ (1 2 0) (3 4 ¯1 1) (7 8 9 11 12)
3 2 1

AutoHotkey[edit]

First_Missing_Positive(obj){
Arr := [], i := 0
for k, v in obj
Arr[v] := true
while (++i<Max(obj*))
if !Arr[i]{
m := i
break
}
m := m ? m : Max(obj*) + 1
return m>0 ? m : 1
}
Examples:
nums := [[1,2,0], [3,4,-1,1], [7,8,9,11,12], [-4,-2,-3], []]
for i, obj in nums{
m := First_Missing_Positive(obj)
output .= m ", "
}
MsgBox % Trim(output, ", ")
return
Output:
3, 2, 1, 1, 1

AWK[edit]

 
# syntax: GAWK -f FIND_FIRST_MISSING_POSITIVE.AWK
BEGIN {
PROCINFO["sorted_in"] = "@ind_num_asc"
nums = "[1,2,0],[3,4,-1,1],[7,8,9,11,12]"
printf("%s : ",nums)
n = split(nums,arr1,"],?") - 1
for (i=1; i<=n; i++) {
gsub(/[\[\]]/,"",arr1[i])
split(arr1[i],arr2,",")
for (j in arr2) {
arr3[arr2[j]]++
}
for (j in arr3) {
if (j <= 0) {
continue
}
if (!(1 in arr3)) {
ans = 1
break
}
if (!(j+1 in arr3)) {
ans = j + 1
break
}
}
printf("%d ",ans)
delete arr3
}
printf("\n")
exit(0)
}
 
Output:
[1,2,0],[3,4,-1,1],[7,8,9,11,12] : 3 2 1

BASIC[edit]

10 DEFINT A-Z: DIM D(100)
20 READ X
30 FOR A=1 TO X
40 READ N
50 FOR I=1 TO N
60 READ D(I)
70 PRINT D(I);
80 NEXT I
90 PRINT "==>";
100 M=1
110 FOR I=1 TO N
120 IF M<D(I) THEN M=D(I)
130 NEXT I
140 FOR I=1 TO M+1
150 FOR J=1 TO N
160 IF D(J)=I GOTO 200
170 NEXT J
180 PRINT I
190 GOTO 210
200 NEXT I
210 NEXT A
220 DATA 3
230 DATA 3, 1,2,0
240 DATA 4, 3,4,-1,1
250 DATA 5, 7,8,9,11,12
Output:
 1  2  0 ==> 3
 3  4 -1  1 ==> 2
 7  8  9  11  12 ==> 1

BCPL[edit]

get "libhdr"
 
let max(v, n) = valof
$( let x = !v
for i=1 to n-1
if x<v!i do x := v!i
resultis x
$)
 
let contains(v, n, el) = valof
$( for i=0 to n-1
if v!i=el resultis true
resultis false
$)
 
let fmp(v, n) = valof
for i=1 to max(v,n)+1
unless contains(v,n,i) resultis i
 
let show(len, v) be
$( for i=0 to len-1 do writef("%N ", v!i)
writef("==> %N*N", fmp(v, len))
$)
 
let start() be
$( show(3, table 1,2,0)
show(4, table 3,4,-1,1)
show(5, table 7,8,9,11,12)
$)
Output:
1 2 0 ==> 3
3 4 -1 1 ==> 2
7 8 9 11 12 ==> 1

F#[edit]

 
// Find first missing positive. Nigel Galloway: February 15., 2021
let fN g=let g=0::g|>List.filter((<) -1)|>List.sort|>List.distinct
match g|>List.pairwise|>List.tryFind(fun(n,g)->g>n+1) with Some(n,_)->n+1 |_->List.max g+1
[[1;2;0];[3;4;-1;1];[7;8;9;11;12]]|>List.iter(fN>>printf "%d "); printfn ""
 
Output:
3 2 1

Factor[edit]

USING: formatting fry hash-sets kernel math sequences sets ;
 
: first-missing ( seq -- n )
>hash-set 1 swap '[ dup _ in? ] [ 1 + ] while ;
 
{ { 1 2 0 } { 3 4 1 1 } { 7 8 9 11 12 } { 1 2 3 4 5 }
{ -6 -5 -2 -1 } { 5 -5 } { -2 } { 1 } { } }
[ dup first-missing "%u ==> %d\n" printf ] each
Output:
{ 1 2 0 } ==> 3
{ 3 4 1 1 } ==> 2
{ 7 8 9 11 12 } ==> 1
{ 1 2 3 4 5 } ==> 6
{ -6 -5 -2 -1 } ==> 1
{ 5 -5 } ==> 1
{ -2 } ==> 1
{ 1 } ==> 2
{ } ==> 1

Go[edit]

Translation of: Wren
package main
 
import (
"fmt"
"sort"
)
 
func firstMissingPositive(a []int) int {
var b []int
for _, e := range a {
if e > 0 {
b = append(b, e)
}
}
sort.Ints(b)
le := len(b)
if le == 0 || b[0] > 1 {
return 1
}
for i := 1; i < le; i++ {
if b[i]-b[i-1] > 1 {
return b[i-1] + 1
}
}
return b[le-1] + 1
}
 
func main() {
fmt.Println("The first missing positive integers for the following arrays are:\n")
aa := [][]int{
{1, 2, 0}, {3, 4, -1, 1}, {7, 8, 9, 11, 12}, {1, 2, 3, 4, 5},
{-6, -5, -2, -1}, {5, -5}, {-2}, {1}, {}}
for _, a := range aa {
fmt.Println(a, "->", firstMissingPositive(a))
}
}
Output:
The first missing positive integers for the following arrays are:

[1 2 0] -> 3
[3 4 -1 1] -> 2
[7 8 9 11 12] -> 1
[1 2 3 4 5] -> 6
[-6 -5 -2 -1] -> 1
[5 -5] -> 1
[-2] -> 1
[1] -> 2
[] -> 1

Haskell[edit]

Translation of: Wren
import Data.List
 
task :: Integral a => [a] -> a
task = go . (0 : ) . sort . filter (> 0)
where
go [x] = x + 1
go (w:xs@(x:_))
| x == w + 1 = go xs
| otherwise = w + 1
 
main = print $ map task [[1,2,0], [3,4,-1,1], [7,8,9,11,12]]
Output:
[3,2,1]

jq[edit]

Works with: jq

Works with gojq, the Go implementation of jq

In case the target array is very long, it probably makes sense either to sort it, or to use a hash, for quick lookup. For the sake of illustration, we'll use a hash:

 
# input: an array of integers
def first_missing_positive:
INDEX(.[]; tostring) as $dict
| first(range(1; infinite)
| . as $n
| select($dict|has($n|tostring)|not) ) ;
 
def examples:
[1,2,0], [3,4,-1,1], [7,8,9,11,12], [-5, -2, -6, -1];
 
# The task:
examples
| "\(first_missing_positive) is missing from \(.)"
Output:
3 is missing from [1,2,0]
2 is missing from [3,4,-1,1]
1 is missing from [7,8,9,11,12]
1 is missing from [-5,-2,-6,-1]

Julia[edit]

 
for array in [[1,2,0], [3,4,-1,1], [7,8,9,11,12], [-5, -2, -6, -1]]
for n in 1:typemax(Int)
 !(n in array) && (println("$array => $n"); break)
end
end
 
Output:
[1, 2, 0]  =>  3
[3, 4, -1, 1]  =>  2
[7, 8, 9, 11, 12]  =>  1
[-5, -2, -6, -1]  =>  1

Nim[edit]

Translation of: Julia

In order to avoid the O(n) search in arrays, we could use an intermediate set built from the sequence. But this is useless with the chosen examples.

for a in [@[1, 2, 0], @[3, 4, -1, 1], @[7, 8, 9, 11, 12], @[-5, -2, -6, -1]]:
for n in 1..int.high:
if n notin a:
echo a, " → ", n
break
Output:
@[1, 2, 0] → 3
@[3, 4, -1, 1] → 2
@[7, 8, 9, 11, 12] → 1
@[-5, -2, -6, -1] → 1

Perl[edit]

#!/usr/bin/perl -l
 
use strict;
use warnings;
use List::Util qw( first );
 
my @tests = ( [1,2,0], [3,4,-1,1], [7,8,9,11,12],
[3, 4, 1, 1], [1, 2, 3, 4, 5], [-6, -5, -2, -1], [5, -5], [-2], [1], []);
 
for my $test ( @tests )
{
print "[ @$test ] ==> ",
first { not { map { $_ => 1 } @$test }->{$_} } 1 .. @$test + 1;
}
Output:
[ 1 2 0 ]  ==>  3
[ 3 4 -1 1 ]  ==>  2
[ 7 8 9 11 12 ]  ==>  1
[ 3 4 1 1 ]  ==>  2
[ 1 2 3 4 5 ]  ==>  6
[ -6 -5 -2 -1 ]  ==>  1
[ 5 -5 ]  ==>  1
[ -2 ]  ==>  1
[ 1 ]  ==>  2
[  ]  ==>  1

Phix[edit]

procedure test(sequence s)
for missing=1 to length(s)+1 do
if not find(missing,s) then
printf(1,"%v -> %v\n",{s,missing})
exit
end if
end for
end procedure
papply({{1,2,0},{3,4,-1,1},{7,8,9,11,12},{1,2,3,4,5},{-6,-5,-2,-1},{5,-5},{-2},{1},{}} ,test)
Output:
{1,2,0} -> 3
{3,4,-1,1} -> 2
{7,8,9,11,12} -> 1
{1,2,3,4,5} -> 6
{-6,-5,-2,-1} -> 1
{5,-5} -> 1
{-2} -> 1
{1} -> 2
{} -> 1

Raku[edit]

say $_, " ==> ", (1..Inf).first( -> \n { n ∉ $_ } ) for
[ 1, 2, 0], [3, 4, 1, 1], [7, 8, 9, 11, 12], [1, 2, 3, 4, 5], [-6, -5, -2, -1], [5, -5], [-2], [1], []
Output:
[1 2 0] ==> 3
[3 4 1 1] ==> 2
[7 8 9 11 12] ==> 1
[1 2 3 4 5] ==> 6
[-6 -5 -2 -1] ==> 1
[5 -5] ==> 1
[-2] ==> 1
[1] ==> 2
[] ==> 1

REXX[edit]

This REXX version doesn't need to sort the elements of the sets,   it uses an associated array.

/*REXX program finds the smallest missing positive integer in a given list of integers. */
parse arg a /*obtain optional arguments from the CL*/
if a='' | a="," then a= '[1,2,0] [3,4,-1,1] [7,8,9,11,12] [1,2,3,4,5]' ,
"[-6,-5,-2,-1] [5,-5] [-2] [1] []" /*maybe use defaults.*/
say 'the smallest missing positive integer for the following sets is:'
say
do j=1 for words(a) /*process each set in a list of sets.*/
set= translate( word(a, j), ,'],[') /*extract a " from " " " " */
#= words(set) /*obtain the number of elements in set.*/
@.= . /*assign default value for set elements*/
do k=1 for #; x= word(set, k) /*obtain a set element (an integer). */
@.x= x /*assign it to a sparse array. */
end /*k*/
 
do m=1 for # until @.m==. /*now, search for the missing integer. */
end /*m*/
if @.m=='' then m= 1 /*handle the case of a "null" set. */
say right( word(a, j), 40) ' ───► ' m /*show the set and the missing integer.*/
end /*j*/ /*stick a fork in it, we're all done. */
output   when using the default inputs:
the smallest missing positive integer for the following sets is:

                                 [1,2,0]  ───►  3
                              [3,4,-1,1]  ───►  2
                           [7,8,9,11,12]  ───►  1
                             [1,2,3,4,5]  ───►  6
                           [-6,-5,-2,-1]  ───►  1
                                  [5,-5]  ───►  1
                                    [-2]  ───►  1
                                     [1]  ───►  2
                                      []  ───►  1

Ring[edit]

 
nums = [[1,2,0],[3,4,-1,1],[7,8,9,11,12]]
numnr = list(3)
numnr[1] = "[1,2,0]"
numnr[2] = "[3,4,-1,1]"
numnr[3] = "[7,8,9,11,12]"
 
for n = 1 to len(nums)
sortNums = sort(nums[n])
ln = len(sortNums)
num = sortNums[ln]
for m = 1 to num + 1
ind = find(nums[n],m)
if ind < 1
see "the smallest missing positive integer for " + numnr[n] + ": " + m + nl
exit
ok
next
next
 
Output:
the smallest missing positive integer for [1,2,0]: 3
the smallest missing positive integer for [3,4,-1,1]: 2
the smallest missing positive integer for [7,8,9,11,12]: 1

Wren[edit]

Library: Wren-sort
import "/sort" for Sort
 
var firstMissingPositive = Fn.new { |a|
var b = a.where { |i| i > 0 }.toList
Sort.insertion(b)
if (b.isEmpty || b[0] > 1) return 1
var i = 1
while (i < b.count) {
if (b[i] - b[i-1] > 1) return b[i-1] + 1
i = i + 1
}
return b[-1] + 1
}
 
System.print("The first missing positive integers for the following arrays are:\n")
var aa = [
[ 1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12], [1, 2, 3, 4, 5],
[-6, -5, -2, -1], [5, -5], [-2], [1], []
]
for (a in aa) System.print("%(a) -> %(firstMissingPositive.call(a))")
Output:
The first missing positive integers for the following arrays are:

[1, 2, 0] -> 3
[3, 4, -1, 1] -> 2
[7, 8, 9, 11, 12] -> 1
[1, 2, 3, 4, 5] -> 6
[-6, -5, -2, -1] -> 1
[5, -5] -> 1
[-2] -> 1
[1] -> 2
[] -> 1