Find first missing positive: Difference between revisions

 

=={{header|11l}}==

 

L(l) nums

I n !C l

print(l‘ -> ’n)

 

{{out}}

 

=={{header|Action!}}==

 

BYTE FUNC Contains(INT ARRAY a INT len,x)

arr(3)=a4 arr(4)=a4

Test(arr,lengths,COUNT)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Find_first_missing_positive.png Screenshot from Atari 8-bit computer]

=={{header|ALGOL 68}}==

Uses the observation in the J sample that the maximum possible minimum missing positive integer is one more than the length of the list.

# returns the lowest positive integer not present in r #

PROC min missing positive = ( []INT r )INT:

print( ( " ", whole( min missing positive( ( 3, 4, -1, 1 ) ), 0 ) ) );

print( ( " ", whole( min missing positive( ( 7, 8, 9, 11, 12 ) ), 0 ) ) )

{{out}}

<pre>

=={{header|APL}}==

{{works with|Dyalog APL}}

{{out}}

<pre> fmp¨ (1 2 0) (3 4 ¯1 1) (7 8 9 11 12)

=={{header|AppleScript}}==

===Procedural===

set output to {}

repeat with aList in {{1, 2, 0}, {3, 4, -1, 1}, {7, 8, 9, 11, 12}}

set end of output to n

end repeat

 

{{output}}

 

 

Defining the value required in terms of pre-existing generic primitives:

 

 

-- firstGap :: [Int] -> Int

set my text item delimiters to dlm

s

{{Out}}

<pre>{1, 2, 0} -> 3

 

=={{header|AutoHotkey}}==

Arr := [], i := 0

for k, v in obj

m := m ? m : Max(obj*) + 1

return m>0 ? m : 1

for i, obj in nums{

m := First_Missing_Positive(obj)

}

MsgBox % Trim(output, ", ")

{{out}}

<pre>3, 2, 1, 1, 1</pre>

 

=={{header|AWK}}==

# syntax: GAWK -f FIND_FIRST_MISSING_POSITIVE.AWK

BEGIN {

exit(0)

}

{{out}}

<pre>

</pre>

=={{header|BASIC}}==

20 READ X

30 FOR A=1 TO X

230 DATA 3, 1,2,0

240 DATA 4, 3,4,-1,1

{{out}}

<pre> 1 2 0 ==> 3

 

=={{header|BCPL}}==

 

let max(v, n) = valof

show(4, table 3,4,-1,1)

show(5, table 7,8,9,11,12)

{{out}}

<pre>1 2 0 ==> 3

 

=={{header|BQN}}==

 

{{out}}

<pre>⟨ 3 2 1 ⟩</pre>

 

=={{header|CLU}}==

where T has equal: proctype (T,T) returns (bool),

U has elements: itertype (U) yields (T)

stream$putl(po, "==> " || int$unparse(fmp[si](test)))

end

{{out}}

<pre>1 2 0 ==> 3

 

=={{header|F_Sharp|F#}}==

// 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 ""

{{out}}

<pre>

 

=={{header|Factor}}==

 

: first-missing ( seq -- n )

{ { 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 } { } }

{{out}}

<pre>

 

=={{header|FreeBASIC}}==

for i as uinteger = 1 to ubound(n)

if n(i) = k then return true

print fmp(a())

print fmp(b())

{{out}}<pre>

3

=={{header|Go}}==

{{trans|Wren}}

 

import (

fmt.Println(a, "->", firstMissingPositive(a))

}

 

{{out}}

=={{header|Haskell}}==

{{trans|Wren}}

 

task :: Integral a => [a] -> a

map

task

{{out}}

<pre>[3,2,1]</pre>

 

Or simply as a filter over an infinite list:

 

firstGap :: [Int] -> Int

[3, 4, -1, 1],

[7, 8, 9, 11, 12]

 

and if xs were large, it could be defined as a set:

 

---------- FIRST MISSING POSITIVE NATURAL NUMBER ---------

firstGap xs = head $ filter (`notMember` seen) [1 ..]

where

{{Out}}

Same output for '''notElem''' and '''notMember''' versions above:

Note that the <nowiki>{{ }}</nowiki> delimiters on definitions was introduced in J version 9.2

 

 

Example use:

 

 

=={{header|JavaScript}}==

"use strict";

 

// MAIN ---

return main();

{{Out}}

<pre>[1,2,0] -> 3

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:

# The task:

examples

{{out}}

<pre>

 

=={{header|Julia}}==

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)

end

end

<pre>

[1, 2, 0] => 3

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 n in 1..int.high:

if n notin a:

echo a, " → ", n

 

{{out}}

 

=={{header|Perl}}==

 

use strict;

print "[ @$test ] ==> ",

first { not { map { $_ => 1 } @$test }->{$_} } 1 .. @$test + 1;

{{out}}

<pre>

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>

<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{}}</span> <span style="color: #0000FF;">,</span><span style="color: #000000;">test</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

 

=={{header|Python}}==

 

from itertools import count

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>[1, 2, 0] -> 3

{{works with|QBasic}}

{{works with|QuickBasic|4.5}}

DECLARE FUNCTION fmp (n())

 

IF n(i) = k THEN isin = 1

NEXT i

{{out}}

<pre>3

 

=={{header|Raku}}==

{{out}}

<pre>[1 2 0] ==> 3

=={{header|REXX}}==

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

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]' ,

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.*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

=={{header|Ring}}==

[-6,-5,-2,-1], [5,-5], [-2], [1], []]

 

if n = len(ary) s = "" ok

res += "" + ary[n] + s

{{out}}

<pre>the smallest missing positive integer for [1,2,0]: 3

 

=={{header|Ruby}}==

{{out}}

<pre>3, 2, 1</pre>

 

=={{header|True BASIC}}==

FOR i = LBOUND(n) TO UBOUND(n)

IF n(i) = k THEN LET isin = 1

DATA 3,4,-1,1

DATA 7,8,9,11,12

 

=={{header|Vlang}}==

{{trans|go}}

mut b := []int{}

for e in a {

println("$a -> ${first_missing_positive(a)}")

}

{{out}}

<pre>Same as go entry</pre>

=={{header|Wren}}==

{{libheader|Wren-sort}}

 

var firstMissingPositive = Fn.new { |a|

[-6, -5, -2, -1], [5, -5], [-2], [1], []

]

 

{{out}}

 

=={{header|XPL0}}==

int Arr, Len, N, N0, I;

[N:= 1;

ShowMissing( Nums(I), (Nums(I+1)-Nums(I))/4 );

];

 

{{out}}