Find first missing positive: Difference between revisions
(Created page with "{{Draft task}} Let given an unsorted integer array nums. The goal is find the smallest missing positive integer. <br> nums = [1,2,0],[3,4,-1,1],[7,8,9,11,12] =={{header|Ring}}...") |
m (Added Easylang) |
||
(83 intermediate revisions by 34 users not shown) | |||
Line 1: | Line 1: | ||
{{Draft task}} |
{{Draft task}} |
||
Let given an unsorted integer array nums. The goal is find the smallest missing positive integer. |
|||
;Task: |
|||
<br> nums = [1,2,0],[3,4,-1,1],[7,8,9,11,12] |
|||
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 |
|||
<br><br> |
|||
=={{header|11l}}== |
|||
<syntaxhighlight lang="11l">V nums = [[1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12]] |
|||
L(l) nums |
|||
L(n) 1.. |
|||
I n !C l |
|||
print(l‘ -> ’n) |
|||
L.break</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1, 2, 0] -> 3 |
|||
[3, 4, -1, 1] -> 2 |
|||
[7, 8, 9, 11, 12] -> 1 |
|||
</pre> |
|||
=={{header|Action!}}== |
|||
<syntaxhighlight lang="action!">DEFINE PTR="CARD" |
|||
BYTE FUNC Contains(INT ARRAY a INT len,x) |
|||
INT i |
|||
FOR i=0 TO len-1 |
|||
DO |
|||
IF a(i)=x THEN |
|||
RETURN (1) |
|||
FI |
|||
OD |
|||
RETURN (0) |
|||
BYTE FUNC FindFirstPositive(INT ARRAY a INT len) |
|||
INT res |
|||
res=1 |
|||
WHILE Contains(a,len,res) |
|||
DO |
|||
res==+1 |
|||
OD |
|||
RETURN (res) |
|||
PROC PrintArray(INT ARRAY a INT len) |
|||
INT i |
|||
Put('[) |
|||
FOR i=0 TO len-1 |
|||
DO |
|||
IF i>0 THEN Put(' ) FI |
|||
PrintI(a(i)) |
|||
OD |
|||
Put(']) |
|||
RETURN |
|||
PROC Test(PTR ARRAY arr INT ARRAY lengths INT count) |
|||
INT ARRAY a |
|||
INT i,len,first |
|||
FOR i=0 TO count-1 |
|||
DO |
|||
a=arr(i) len=lengths(i) |
|||
PrintArray(a,len) |
|||
Print(" -> ") |
|||
first=FindFirstPositive(a,len) |
|||
PrintIE(first) |
|||
OD |
|||
RETURN |
|||
PROC Main() |
|||
DEFINE COUNT="5" |
|||
PTR ARRAY arr(COUNT) |
|||
INT ARRAY |
|||
lengths=[3 4 5 3 0], |
|||
a1=[1 2 0], |
|||
a2=[3 4 65535 1], |
|||
a3=[7 8 9 11 12], |
|||
a4=[65534 65530 65520] |
|||
arr(0)=a1 arr(1)=a2 arr(2)=a3 |
|||
arr(3)=a4 arr(4)=a4 |
|||
Test(arr,lengths,COUNT) |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Find_first_missing_positive.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
[1 2 0] -> 3 |
|||
[3 4 -1 1] -> 2 |
|||
[7 8 9 11 12] -> 1 |
|||
[-2 -6 -16] -> 1 |
|||
[] -> 1 |
|||
</pre> |
|||
=={{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. |
|||
<syntaxhighlight lang="algol68">BEGIN # find the lowest positive integer not present in various arrays # |
|||
# returns the lowest positive integer not present in r # |
|||
PROC min missing positive = ( []INT r )INT: |
|||
BEGIN |
|||
[]INT a = r[ AT 1 ]; # a is r wih lower bound 1 # |
|||
# as noted in the J sample, the maximum possible minimum # |
|||
# missing positive integer is one more than the length of the array # |
|||
# note the values between 1 and UPB a present in a # |
|||
[ 1 : UPB a ]BOOL present; |
|||
FOR i TO UPB a DO present[ i ] := FALSE OD; |
|||
FOR i TO UPB a DO |
|||
INT ai = a[ i ]; |
|||
IF ai >= 1 AND ai <= UPB a THEN |
|||
present[ ai ] := TRUE |
|||
FI |
|||
OD; |
|||
# find the lowest value not in present # |
|||
INT result := UPB a + 1; |
|||
BOOL found := FALSE; |
|||
FOR i TO UPB a WHILE NOT found DO |
|||
IF NOT present[ i ] THEN |
|||
found := TRUE; |
|||
result := i |
|||
FI |
|||
OD; |
|||
result |
|||
END # min missing positive # ; |
|||
print( ( " ", whole( min missing positive( ( 1, 2, 0 ) ), 0 ) ) ); |
|||
print( ( " ", whole( min missing positive( ( 3, 4, -1, 1 ) ), 0 ) ) ); |
|||
print( ( " ", whole( min missing positive( ( 7, 8, 9, 11, 12 ) ), 0 ) ) ) |
|||
END</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
3 2 1 |
|||
</pre> |
|||
=={{header|APL}}== |
|||
{{works with|Dyalog APL}} |
|||
<syntaxhighlight lang="apl">fmp ← ⊃(⍳1+⌈/)~⊢</syntaxhighlight> |
|||
{{out}} |
|||
<pre> fmp¨ (1 2 0) (3 4 ¯1 1) (7 8 9 11 12) |
|||
3 2 1</pre> |
|||
=={{header|AppleScript}}== |
|||
===Procedural=== |
|||
<syntaxhighlight lang="applescript">local output, aList, n |
|||
set output to {} |
|||
repeat with aList in {{1, 2, 0}, {3, 4, -1, 1}, {7, 8, 9, 11, 12}} |
|||
set n to 1 |
|||
repeat while (aList contains n) |
|||
set n to n + 1 |
|||
end repeat |
|||
set end of output to n |
|||
end repeat |
|||
return output</syntaxhighlight> |
|||
{{output}} |
|||
<syntaxhighlight lang="applescript">{3, 2, 1}</syntaxhighlight> |
|||
===Functional=== |
|||
Defining the value required in terms of pre-existing generic primitives: |
|||
<syntaxhighlight lang="applescript">--------------- FIRST MISSING NATURAL NUMBER ------------- |
|||
-- firstGap :: [Int] -> Int |
|||
on firstGap(xs) |
|||
script p |
|||
on |λ|(x) |
|||
xs does not contain x |
|||
end |λ| |
|||
end script |
|||
find(p, enumFrom(1)) |
|||
end firstGap |
|||
--------------------------- TEST ------------------------- |
|||
on run |
|||
script test |
|||
on |λ|(xs) |
|||
showList(xs) & " -> " & (firstGap(xs) as string) |
|||
end |λ| |
|||
end script |
|||
unlines(map(test, ¬ |
|||
{{1, 2, 0}, {3, 4, -1, 1}, {7, 8, 9, 11, 12}})) |
|||
--> {1, 2, 0} -> 3 |
|||
--> {3, 4, -1, 1} -> 2 |
|||
--> {7, 8, 9, 11, 12} -> 1 |
|||
end run |
|||
------------------------- GENERIC ------------------------ |
|||
-- enumFrom :: Enum a => a -> [a] |
|||
on enumFrom(x) |
|||
script |
|||
property v : missing value |
|||
on |λ|() |
|||
if missing value is not v then |
|||
set v to 1 + v |
|||
else |
|||
set v to x |
|||
end if |
|||
return v |
|||
end |λ| |
|||
end script |
|||
end enumFrom |
|||
-- find :: (a -> Bool) -> Gen [a] -> Maybe a |
|||
on find(p, gen) |
|||
-- The first match for the predicate p |
|||
-- in the generator stream gen, or missing value |
|||
-- if no match is found. |
|||
set mp to mReturn(p) |
|||
set v to gen's |λ|() |
|||
repeat until missing value is v or (|λ|(v) of mp) |
|||
set v to (|λ|() of gen) |
|||
end repeat |
|||
v |
|||
end find |
|||
-- intercalate :: String -> [String] -> String |
|||
on intercalate(delim, xs) |
|||
set {dlm, my text item delimiters} to ¬ |
|||
{my text item delimiters, delim} |
|||
set s to xs as text |
|||
set my text item delimiters to dlm |
|||
s |
|||
end intercalate |
|||
-- map :: (a -> b) -> [a] -> [b] |
|||
on map(f, xs) |
|||
-- The list obtained by applying f |
|||
-- to each element of xs. |
|||
tell mReturn(f) |
|||
set lng to length of xs |
|||
set lst to {} |
|||
repeat with i from 1 to lng |
|||
set end of lst to |λ|(item i of xs, i, xs) |
|||
end repeat |
|||
return lst |
|||
end tell |
|||
end map |
|||
-- mReturn :: First-class m => (a -> b) -> m (a -> b) |
|||
on mReturn(f) |
|||
-- 2nd class handler function lifted into 1st class script wrapper. |
|||
if script is class of f then |
|||
f |
|||
else |
|||
script |
|||
property |λ| : f |
|||
end script |
|||
end if |
|||
end mReturn |
|||
-- showList :: [a] -> String |
|||
on showList(xs) |
|||
script go |
|||
on |λ|(x) |
|||
x as string |
|||
end |λ| |
|||
end script |
|||
"{" & intercalate(", ", map(go, xs)) & "}" |
|||
end showList |
|||
-- unlines :: [String] -> String |
|||
on unlines(xs) |
|||
-- A single string formed by the intercalation |
|||
-- of a list of strings with the newline character. |
|||
set {dlm, my text item delimiters} to ¬ |
|||
{my text item delimiters, linefeed} |
|||
set s to xs as text |
|||
set my text item delimiters to dlm |
|||
s |
|||
end unlines</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>{1, 2, 0} -> 3 |
|||
{3, 4, -1, 1} -> 2 |
|||
{7, 8, 9, 11, 12} -> 1</pre> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="arturo">sets: @[[1 2 0] @[3 4 neg 1 1] [7 8 9 11 12]] |
|||
loop sets 's -> |
|||
print [ |
|||
"Set:" s |
|||
"-> First missing positive integer:" first select.first 1..∞ 'x -> not? in? x s |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Set: [1 2 0] -> First missing positive integer: 3 |
|||
Set: [3 4 -1 1] -> First missing positive integer: 2 |
|||
Set: [7 8 9 11 12] -> First missing positive integer: 1</pre> |
|||
=={{header|AutoHotkey}}== |
|||
<syntaxhighlight lang="autohotkey">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 |
|||
}</syntaxhighlight> |
|||
Examples:<syntaxhighlight lang="autohotkey">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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3, 2, 1, 1, 1</pre> |
|||
=={{header|AWK}}== |
|||
<syntaxhighlight lang="awk"> |
|||
# 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) |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1,2,0],[3,4,-1,1],[7,8,9,11,12] : 3 2 1 |
|||
</pre> |
|||
=={{header|BASIC}}== |
|||
<syntaxhighlight lang="basic">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</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 1 2 0 ==> 3 |
|||
3 4 -1 1 ==> 2 |
|||
7 8 9 11 12 ==> 1</pre> |
|||
=={{header|BCPL}}== |
|||
<syntaxhighlight lang="bcpl">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) |
|||
$)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>1 2 0 ==> 3 |
|||
3 4 -1 1 ==> 2 |
|||
7 8 9 11 12 ==> 1</pre> |
|||
=={{header|BQN}}== |
|||
<syntaxhighlight lang="bqn">FMP ← ⊢(⊑(¬∊˜ )/⊢)1+(↕1+⌈´) |
|||
FMP¨ ⟨⟨1,2,0⟩,⟨3,4,¯1,1⟩,⟨7,8,9,11,12⟩⟩</syntaxhighlight> |
|||
{{out}} |
|||
<pre>⟨ 3 2 1 ⟩</pre> |
|||
=={{header|C++}}== |
|||
<syntaxhighlight lang="cpp">#include <iostream> |
|||
#include <unordered_set> |
|||
#include <vector> |
|||
int FindFirstMissing(const std::vector<int>& r) |
|||
{ |
|||
// put them into an associative container |
|||
std::unordered_set us(r.begin(), r.end()); |
|||
size_t result = 0; |
|||
while (us.contains(++result)); // find the first number that isn't there |
|||
return (int)result; |
|||
} |
|||
int main() |
|||
{ |
|||
std::vector<std::vector<int>> nums {{1,2,0}, {3,4,-1,1}, {7,8,9,11,12}}; |
|||
std::for_each(nums.begin(), nums.end(), |
|||
[](auto z){std::cout << FindFirstMissing(z) << " "; }); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
3 2 1 </pre> |
|||
=={{header|CLU}}== |
|||
<syntaxhighlight lang="clu">contains = proc [T, U: type] (needle: T, haystack: U) returns (bool) |
|||
where T has equal: proctype (T,T) returns (bool), |
|||
U has elements: itertype (U) yields (T) |
|||
for item: T in U$elements(haystack) do |
|||
if item = needle then return(true) end |
|||
end |
|||
return(false) |
|||
end contains |
|||
fmp = proc [T: type] (list: T) returns (int) |
|||
where T has elements: itertype (T) yields (int) |
|||
n: int := 1 |
|||
while contains[int, T](n, list) do |
|||
n := n + 1 |
|||
end |
|||
return(n) |
|||
end fmp |
|||
start_up = proc () |
|||
si = sequence[int] |
|||
ssi = sequence[si] |
|||
po: stream := stream$primary_output() |
|||
tests: ssi := ssi$[si$[1,2,0], si$[3,4,-1,1], si$[7,8,9,11,12]] |
|||
for test: si in ssi$elements(tests) do |
|||
for i: int in si$elements(test) do |
|||
stream$puts(po, int$unparse(i) || " ") |
|||
end |
|||
stream$putl(po, "==> " || int$unparse(fmp[si](test))) |
|||
end |
|||
end start_up</syntaxhighlight> |
|||
{{out}} |
|||
<pre>1 2 0 ==> 3 |
|||
3 4 -1 1 ==> 2 |
|||
7 8 9 11 12 ==> 1</pre> |
|||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
Uses the Delphi "TList" object to search the list for missing integers. |
|||
<syntaxhighlight lang="Delphi"> |
|||
var List1: array [0..2] of integer =(1,2,0); |
|||
var List2: array [0..3] of integer =(3,4,-1,1); |
|||
var List3: array [0..4] of integer =(7,8,9,11,12); |
|||
function FindMissingInt(IA: array of integer): integer; |
|||
var I,Inx: integer; |
|||
var List: TList; |
|||
begin |
|||
List:=TList.Create; |
|||
try |
|||
Result:=-1; |
|||
for I:=0 to High(IA) do List.Add(Pointer(IA[I])); |
|||
for Result:=1 to High(integer) do |
|||
begin |
|||
Inx:=List.IndexOf(Pointer(Result)); |
|||
if Inx<0 then exit; |
|||
end; |
|||
finally List.Free; end; |
|||
end; |
|||
function GetIntStr(IA: array of integer): string; |
|||
var I: integer; |
|||
begin |
|||
Result:='['; |
|||
for I:=0 to High(IA) do |
|||
begin |
|||
if I>0 then Result:=Result+','; |
|||
Result:=Result+Format('%3.0d',[IA[I]]); |
|||
end; |
|||
Result:=Result+']'; |
|||
end; |
|||
procedure ShowMissingInts(Memo: TMemo); |
|||
var S: string; |
|||
var M: integer; |
|||
begin |
|||
S:=GetIntStr(List1); |
|||
M:=FindMissingInt(List1); |
|||
Memo.Lines.Add(S+' = '+IntToStr(M)); |
|||
S:=GetIntStr(List2); |
|||
M:=FindMissingInt(List2); |
|||
Memo.Lines.Add(S+' = '+IntToStr(M)); |
|||
S:=GetIntStr(List3); |
|||
M:=FindMissingInt(List3); |
|||
Memo.Lines.Add(S+' = '+IntToStr(M)); |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[ 1, 2, 0] = 3 |
|||
[ 3, 4, -1, 1] = 2 |
|||
[ 7, 8, 9, 11, 12] = 1 |
|||
</pre> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight> |
|||
func missing a[] . |
|||
h = 1 |
|||
repeat |
|||
v = 0 |
|||
for v in a[] |
|||
if h = v |
|||
break 1 |
|||
. |
|||
. |
|||
until v <> h |
|||
h += 1 |
|||
. |
|||
return h |
|||
. |
|||
a[][] = [ [ 1 2 0 ] [ 3 4 -1 1 ] [ 7 8 9 11 12 ] ] |
|||
for i to len a[][] |
|||
write missing a[i][] & " " |
|||
. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
3 2 1 |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
|||
<syntaxhighlight lang="fsharp"> |
|||
// 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 "" |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
3 2 1 |
|||
</pre> |
|||
=={{header|Factor}}== |
|||
<syntaxhighlight lang="factor">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</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
{ 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 |
|||
</pre> |
|||
=={{header|FreeBASIC}}== |
|||
<syntaxhighlight lang="freebasic">function is_in( n() as integer, k as uinteger ) as boolean |
|||
for i as uinteger = 1 to ubound(n) |
|||
if n(i) = k then return true |
|||
next i |
|||
return false |
|||
end function |
|||
function fmp( n() as integer ) as integer |
|||
dim as uinteger i = 1 |
|||
while is_in( n(), i ) |
|||
i+=1 |
|||
wend |
|||
return i |
|||
end function |
|||
dim as integer a(1 to 3) = {1, 2, 0} |
|||
dim as integer b(1 to 4) = {3, 4, -1, 1} |
|||
dim as integer c(1 to 5) = {7, 8, 9, 11, 12} |
|||
print fmp(a()) |
|||
print fmp(b()) |
|||
print fmp(c())</syntaxhighlight> |
|||
{{out}}<pre> |
|||
3 |
|||
2 |
|||
1 |
|||
</pre> |
|||
=={{header|Go}}== |
|||
{{trans|Wren}} |
|||
<syntaxhighlight lang="go">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)) |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Haskell}}== |
|||
{{trans|Wren}} |
|||
<syntaxhighlight lang="haskell">import Data.List (sort) |
|||
task :: Integral a => [a] -> a |
|||
task = go . (0 :) . sort . filter (> 0) |
|||
where |
|||
go [x] = succ x |
|||
go (w : xs@(x : _)) |
|||
| x == succ w = go xs |
|||
| otherwise = succ w |
|||
main :: IO () |
|||
main = |
|||
print $ |
|||
map |
|||
task |
|||
[[1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12]]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[3,2,1]</pre> |
|||
Or simply as a filter over an infinite list: |
|||
<syntaxhighlight lang="haskell">---------- FIRST MISSING POSITIVE NATURAL NUMBER --------- |
|||
firstGap :: [Int] -> Int |
|||
firstGap xs = head $ filter (`notElem` xs) [1 ..] |
|||
--------------------------- TEST ------------------------- |
|||
main :: IO () |
|||
main = |
|||
(putStrLn . unlines) $ |
|||
fmap |
|||
(\xs -> show xs <> " -> " <> (show . firstGap) xs) |
|||
[ [1, 2, 0], |
|||
[3, 4, -1, 1], |
|||
[7, 8, 9, 11, 12] |
|||
]</syntaxhighlight> |
|||
and if xs were large, it could be defined as a set: |
|||
<syntaxhighlight lang="haskell">import Data.Set (fromList, notMember) |
|||
---------- FIRST MISSING POSITIVE NATURAL NUMBER --------- |
|||
firstGap :: [Int] -> Int |
|||
firstGap xs = head $ filter (`notMember` seen) [1 ..] |
|||
where |
|||
seen = fromList xs</syntaxhighlight> |
|||
{{Out}} |
|||
Same output for '''notElem''' and '''notMember''' versions above: |
|||
<pre>[1,2,0] -> 3 |
|||
[3,4,-1,1] -> 2 |
|||
[7,8,9,11,12] -> 1</pre> |
|||
=={{header|J}}== |
|||
The first missing positive can be no larger than 1 plus the length of the list, thus: |
|||
<syntaxhighlight lang="j">fmp=: {{ {.y-.~1+i.1+#y }}S:0</syntaxhighlight> |
|||
(The <nowiki>{{ }}</nowiki> delimiters on definitions, used here, was introduced in J version 9.2) |
|||
Example use: |
|||
<syntaxhighlight lang="j"> fmp 1 2 0;3 4 _1 1; 7 8 9 11 12 |
|||
3 2 1</syntaxhighlight> |
|||
Also, with this approach: |
|||
<syntaxhighlight lang=J> fmp 'abc' |
|||
1</syntaxhighlight> |
|||
=={{header|JavaScript}}== |
|||
<syntaxhighlight lang="javascript">(() => { |
|||
"use strict"; |
|||
// ---------- FIRST MISSING NATURAL NUMBER ----------- |
|||
// firstGap :: [Int] -> Int |
|||
const firstGap = xs => { |
|||
const seen = new Set(xs); |
|||
return filterGen( |
|||
x => !seen.has(x) |
|||
)( |
|||
enumFrom(1) |
|||
) |
|||
.next() |
|||
.value; |
|||
}; |
|||
// ---------------------- TEST ----------------------- |
|||
// main :: IO () |
|||
const main = () => [ |
|||
[1, 2, 0], |
|||
[3, 4, -1, 1], |
|||
[7, 8, 9, 11, 12] |
|||
] |
|||
.map(xs => `${show(xs)} -> ${firstGap(xs)}`) |
|||
.join("\n"); |
|||
// --------------------- GENERIC --------------------- |
|||
// enumFrom :: Int -> [Int] |
|||
const enumFrom = function* (x) { |
|||
// A non-finite succession of |
|||
// integers, starting with n. |
|||
let v = x; |
|||
while (true) { |
|||
yield v; |
|||
v = 1 + v; |
|||
} |
|||
}; |
|||
// filterGen :: (a -> Bool) -> Gen [a] -> Gen [a] |
|||
const filterGen = p => |
|||
// A stream of values which are drawn |
|||
// from a generator, and satisfy p. |
|||
xs => { |
|||
const go = function* () { |
|||
let x = xs.next(); |
|||
while (!x.done) { |
|||
const v = x.value; |
|||
if (p(v)) { |
|||
yield v; |
|||
} |
|||
x = xs.next(); |
|||
} |
|||
}; |
|||
return go(xs); |
|||
}; |
|||
// show :: a -> String |
|||
const show = x => JSON.stringify(x); |
|||
// MAIN --- |
|||
return main(); |
|||
})();</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>[1,2,0] -> 3 |
|||
[3,4,-1,1] -> 2 |
|||
[7,8,9,11,12] -> 1</pre> |
|||
=={{header|jq}}== |
|||
{{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: |
|||
<syntaxhighlight lang="jq"> |
|||
# 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 \(.)"</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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] |
|||
</pre> |
|||
=={{header|Julia}}== |
|||
<syntaxhighlight lang="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) |
|||
!(n in array) && (println("$array => $n"); break) |
|||
end |
|||
end |
|||
</syntaxhighlight>{{out}} |
|||
<pre> |
|||
[1, 2, 0] => 3 |
|||
[3, 4, -1, 1] => 2 |
|||
[7, 8, 9, 11, 12] => 1 |
|||
[-5, -2, -6, -1] => 1 |
|||
</pre> |
|||
=={{header|Nim}}== |
|||
{{trans|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. |
|||
<syntaxhighlight lang="nim">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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>@[1, 2, 0] → 3 |
|||
@[3, 4, -1, 1] → 2 |
|||
@[7, 8, 9, 11, 12] → 1 |
|||
@[-5, -2, -6, -1] → 1</pre> |
|||
=={{header|Perl}}== |
|||
<syntaxhighlight lang="perl">#!/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; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[ 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 |
|||
</pre> |
|||
=={{header|Phix}}== |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<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;">for</span> <span style="color: #000000;">missing</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">missing</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%v -> %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">missing</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #008080;">exit</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
{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 |
|||
</pre> |
|||
=={{header|Python}}== |
|||
<syntaxhighlight lang="python">'''First missing natural number''' |
|||
from itertools import count |
|||
# firstGap :: [Int] -> Int |
|||
def firstGap(xs): |
|||
'''First natural number not found in xs''' |
|||
return next(x for x in count(1) if x not in xs) |
|||
# ------------------------- TEST ------------------------- |
|||
# main :: IO () |
|||
def main(): |
|||
'''First missing natural number in each list''' |
|||
print('\n'.join([ |
|||
f'{repr(xs)} -> {firstGap(xs)}' for xs in [ |
|||
[1, 2, 0], |
|||
[3, 4, -1, 1], |
|||
[7, 8, 9, 11, 12] |
|||
] |
|||
])) |
|||
# MAIN --- |
|||
if __name__ == '__main__': |
|||
main()</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>[1, 2, 0] -> 3 |
|||
[3, 4, -1, 1] -> 2 |
|||
[7, 8, 9, 11, 12] -> 1</pre> |
|||
=={{header|QBasic}}== |
|||
{{works with|QBasic}} |
|||
{{works with|QuickBasic|4.5}} |
|||
<syntaxhighlight lang="qbasic">DECLARE FUNCTION isin (n(), k) |
|||
DECLARE FUNCTION fmp (n()) |
|||
DIM a(3) |
|||
FOR x = 1 TO UBOUND(a): READ a(x): NEXT x |
|||
DIM b(4) |
|||
FOR x = 1 TO UBOUND(b): READ b(x): NEXT x |
|||
DIM c(5) |
|||
FOR x = 1 TO UBOUND(c): READ c(x): NEXT x |
|||
PRINT fmp(a()) |
|||
PRINT fmp(b()) |
|||
PRINT fmp(c()) |
|||
Sleep |
|||
END |
|||
DATA 1,2,0 |
|||
DATA 3,4,-1,1 |
|||
DATA 7,8,9,11,12 |
|||
FUNCTION fmp (n()) |
|||
j = 1 |
|||
WHILE isin(n(), j) |
|||
j = j + 1 |
|||
WEND |
|||
fmp = j |
|||
END FUNCTION |
|||
FUNCTION isin (n(), k) |
|||
FOR i = LBOUND(n) TO UBOUND(n) |
|||
IF n(i) = k THEN isin = 1 |
|||
NEXT i |
|||
END FUNCTION</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3 |
|||
2 |
|||
1</pre> |
|||
=={{header|Quackery}}== |
|||
===Using a bitmap as a set=== |
|||
Treat a number (BigInt) as a set of integers. Add the positive integers to the set, then find the first positive integer not in the set. |
|||
<syntaxhighlight lang="Quackery"> [ 0 0 rot |
|||
witheach |
|||
[ dup 0 > iff |
|||
[ bit | ] |
|||
else drop ] |
|||
[ dip 1+ |
|||
1 >> dup 1 & |
|||
0 = until ] |
|||
drop ] is task ( [ --> n ) |
|||
' [ [ 1 2 0 ] [ 3 4 -1 1 ] [ 7 8 9 11 12 ] ] |
|||
witheach [ task echo sp ]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3 2 1</pre> |
|||
===Using filtering and sorting=== |
|||
Filter out the non-positive integers, and then non-unique elements (after adding zero). |
|||
<code>uniquewith</code> is defined at [[Remove duplicate elements#Quackery]] and conveniently sorts the nest. |
|||
Then hunt for the first item which does not have the same value as its index. If they all have the same values as their indices, the missing integer is the same as the size of the processed nest. |
|||
<syntaxhighlight lang="Quackery"> [ [] swap |
|||
witheach |
|||
[ dup 0 > iff |
|||
join |
|||
else drop ] |
|||
0 join |
|||
uniquewith > |
|||
dup size swap |
|||
witheach |
|||
[ i^ != if |
|||
[ drop i^ |
|||
conclude ] ] ] is task ( [ --> n ) |
|||
' [ [ 1 2 0 ] [ 3 4 -1 1 ] [ 7 8 9 11 12 ] ] |
|||
witheach [ task echo sp ]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3 2 1</pre> |
|||
===Brute force=== |
|||
Search for each integer. The largest the missing integer can be is one more than the number of items in the nest. |
|||
<syntaxhighlight lang="Quackery"> [ dup size |
|||
dup 1+ unrot |
|||
times |
|||
[ i^ 1+ |
|||
over find |
|||
over found not if |
|||
[ dip |
|||
[ drop i^ 1+ ] |
|||
conclude ] ] |
|||
drop ] is task ( [ --> n ) |
|||
' [ [ 1 2 0 ] [ 3 4 -1 1 ] [ 7 8 9 11 12 ] ] |
|||
witheach [ task echo sp ]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3 2 1</pre> |
|||
=={{header|Raku}}== |
|||
<syntaxhighlight lang="raku" line>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], []</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[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</pre> |
|||
=={{header|REXX}}== |
|||
This REXX version doesn't need to sort the elements of the sets, it uses an associated array. |
|||
<syntaxhighlight lang="rexx">/*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. */</syntaxhighlight> |
|||
{{out|output|text= when using the default inputs:}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
<syntaxhighlight lang="ring">nums = [[1,2,0], [3,4,-1,1], [7,8,9,11,12], [1,2,3,4,5], |
|||
<lang ring> |
|||
[-6,-5,-2,-1], [5,-5], [-2], [1], []] |
|||
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) |
for n = 1 to len(nums) |
||
see "the smallest missing positive integer for " |
|||
for m = 1 to len(nums[n]) |
|||
? (arrayToStr(nums[n]) + ": " + fmp(nums[n])) |
|||
del(nums[n],m) |
|||
ok |
|||
next |
|||
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 |
next |
||
</lang> |
|||
func fmp(ary) |
|||
if len(ary) > 0 |
|||
for m = 1 to max(ary) + 1 |
|||
if find(ary, m) < 1 return m ok |
|||
next ok return 1 |
|||
func arrayToStr(ary) |
|||
res = "[" s = "," |
|||
for n = 1 to len(ary) |
|||
if n = len(ary) s = "" ok |
|||
res += "" + ary[n] + s |
|||
next return res + "]"</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre>the smallest missing positive integer for [1,2,0]: 3 |
|||
<pre> |
|||
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 [3,4,-1,1]: 2 |
||
the smallest missing positive integer for [7,8,9,11,12]: 1 |
the smallest missing positive integer for [7,8,9,11,12]: 1 |
||
the smallest missing positive integer for [1,2,3,4,5]: 6 |
|||
the smallest missing positive integer for [-6,-5,-2,-1]: 1 |
|||
the smallest missing positive integer for [5,-5]: 1 |
|||
the smallest missing positive integer for [-2]: 1 |
|||
the smallest missing positive integer for [1]: 2 |
|||
the smallest missing positive integer for []: 1</pre> |
|||
=={{header|RPL}}== |
|||
≪ 1 '''WHILE''' DUP2 POS '''REPEAT''' 1 + '''END''' SWAP DROP ≫ '<span style="color:blue">FINDF</span>' STO |
|||
{ { 1 2 0 } { 3 4 -1 1 } { 7 8 9 11 12 } } 1 ≪ <span style="color:blue">FINDF</span> ≫ DOLIST |
|||
{{out}} |
|||
<pre> |
|||
1: { 3 2 1 } |
|||
</pre> |
|||
=={{header|Ruby}}== |
|||
<syntaxhighlight lang="ruby">nums = [1,2,0], [3,4,-1,1], [7,8,9,11,12] |
|||
puts nums.map{|ar|(1..).find{|candidate| !ar.include?(candidate) }}.join(", ")</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3, 2, 1</pre> |
|||
=={{header|Sidef}}== |
|||
<syntaxhighlight lang="ruby">[[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], []].each {|arr| |
|||
var s = Set(arr...) |
|||
say (arr, " ==> ", 1..Inf -> first {|k| !s.has(k) }) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[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</pre> |
|||
=={{header|True BASIC}}== |
|||
<syntaxhighlight lang="qbasic">FUNCTION isin (n(), k) |
|||
FOR i = LBOUND(n) TO UBOUND(n) |
|||
IF n(i) = k THEN LET isin = 1 |
|||
NEXT i |
|||
END FUNCTION |
|||
FUNCTION fmp (n()) |
|||
LET j = 1 |
|||
DO WHILE isin(n(), j) = 1 |
|||
LET j = j + 1 |
|||
LOOP |
|||
LET fmp = j |
|||
END FUNCTION |
|||
DIM a(3) |
|||
FOR x = 1 TO UBOUND(a) |
|||
READ a(x) |
|||
NEXT x |
|||
DIM b(4) |
|||
FOR x = 1 TO UBOUND(b) |
|||
READ b(x) |
|||
NEXT x |
|||
DIM c(5) |
|||
FOR x = 1 TO UBOUND(c) |
|||
READ c(x) |
|||
NEXT x |
|||
PRINT fmp(a()) |
|||
PRINT fmp(b()) |
|||
PRINT fmp(c()) |
|||
DATA 1,2,0 |
|||
DATA 3,4,-1,1 |
|||
DATA 7,8,9,11,12 |
|||
END</syntaxhighlight> |
|||
=={{header|V (Vlang)}}== |
|||
{{trans|go}} |
|||
<syntaxhighlight lang="v (vlang)">fn first_missing_positive(a []int) int { |
|||
mut b := []int{} |
|||
for e in a { |
|||
if e > 0 { |
|||
b << e |
|||
} |
|||
} |
|||
b.sort<int>() |
|||
le := b.len |
|||
if le == 0 || b[0] > 1 { |
|||
return 1 |
|||
} |
|||
for i in 1..le { |
|||
if b[i]-b[i-1] > 1 { |
|||
return b[i-1] + 1 |
|||
} |
|||
} |
|||
return b[le-1] + 1 |
|||
} |
|||
fn main() { |
|||
println("The first missing positive integers for the following arrays are:\n") |
|||
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 { |
|||
println("$a -> ${first_missing_positive(a)}") |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as go entry</pre> |
|||
=={{header|Wren}}== |
|||
{{libheader|Wren-sort}} |
|||
<syntaxhighlight lang="wren">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))")</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
<syntaxhighlight lang="xpl0">proc ShowMissing(Arr, Len); |
|||
int Arr, Len, N, N0, I; |
|||
[N:= 1; |
|||
repeat N0:= N; |
|||
for I:= 0 to Len-1 do |
|||
if Arr(I) = N then N:= N+1; |
|||
until N = N0; |
|||
IntOut(0, N); ChOut(0, ^ ); |
|||
]; |
|||
int I, Nums; |
|||
[for I:= 0 to 2 do |
|||
[Nums:= [[1,2,0], [3,4,-1,1], [7,8,9,11,12], [0]]; |
|||
ShowMissing( Nums(I), (Nums(I+1)-Nums(I))/4 ); |
|||
]; |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
3 2 1 |
|||
</pre> |
</pre> |
Latest revision as of 11:32, 15 April 2024
- 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
11l
V nums = [[1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12]]
L(l) nums
L(n) 1..
I n !C l
print(l‘ -> ’n)
L.break
- Output:
[1, 2, 0] -> 3 [3, 4, -1, 1] -> 2 [7, 8, 9, 11, 12] -> 1
Action!
DEFINE PTR="CARD"
BYTE FUNC Contains(INT ARRAY a INT len,x)
INT i
FOR i=0 TO len-1
DO
IF a(i)=x THEN
RETURN (1)
FI
OD
RETURN (0)
BYTE FUNC FindFirstPositive(INT ARRAY a INT len)
INT res
res=1
WHILE Contains(a,len,res)
DO
res==+1
OD
RETURN (res)
PROC PrintArray(INT ARRAY a INT len)
INT i
Put('[)
FOR i=0 TO len-1
DO
IF i>0 THEN Put(' ) FI
PrintI(a(i))
OD
Put('])
RETURN
PROC Test(PTR ARRAY arr INT ARRAY lengths INT count)
INT ARRAY a
INT i,len,first
FOR i=0 TO count-1
DO
a=arr(i) len=lengths(i)
PrintArray(a,len)
Print(" -> ")
first=FindFirstPositive(a,len)
PrintIE(first)
OD
RETURN
PROC Main()
DEFINE COUNT="5"
PTR ARRAY arr(COUNT)
INT ARRAY
lengths=[3 4 5 3 0],
a1=[1 2 0],
a2=[3 4 65535 1],
a3=[7 8 9 11 12],
a4=[65534 65530 65520]
arr(0)=a1 arr(1)=a2 arr(2)=a3
arr(3)=a4 arr(4)=a4
Test(arr,lengths,COUNT)
RETURN
- Output:
Screenshot from Atari 8-bit computer
[1 2 0] -> 3 [3 4 -1 1] -> 2 [7 8 9 11 12] -> 1 [-2 -6 -16] -> 1 [] -> 1
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.
BEGIN # find the lowest positive integer not present in various arrays #
# returns the lowest positive integer not present in r #
PROC min missing positive = ( []INT r )INT:
BEGIN
[]INT a = r[ AT 1 ]; # a is r wih lower bound 1 #
# as noted in the J sample, the maximum possible minimum #
# missing positive integer is one more than the length of the array #
# note the values between 1 and UPB a present in a #
[ 1 : UPB a ]BOOL present;
FOR i TO UPB a DO present[ i ] := FALSE OD;
FOR i TO UPB a DO
INT ai = a[ i ];
IF ai >= 1 AND ai <= UPB a THEN
present[ ai ] := TRUE
FI
OD;
# find the lowest value not in present #
INT result := UPB a + 1;
BOOL found := FALSE;
FOR i TO UPB a WHILE NOT found DO
IF NOT present[ i ] THEN
found := TRUE;
result := i
FI
OD;
result
END # min missing positive # ;
print( ( " ", whole( min missing positive( ( 1, 2, 0 ) ), 0 ) ) );
print( ( " ", whole( min missing positive( ( 3, 4, -1, 1 ) ), 0 ) ) );
print( ( " ", whole( min missing positive( ( 7, 8, 9, 11, 12 ) ), 0 ) ) )
END
- Output:
3 2 1
APL
fmp ← ⊃(⍳1+⌈/)~⊢
- Output:
fmp¨ (1 2 0) (3 4 ¯1 1) (7 8 9 11 12) 3 2 1
AppleScript
Procedural
local output, aList, n
set output to {}
repeat with aList in {{1, 2, 0}, {3, 4, -1, 1}, {7, 8, 9, 11, 12}}
set n to 1
repeat while (aList contains n)
set n to n + 1
end repeat
set end of output to n
end repeat
return output
- Output:
{3, 2, 1}
Functional
Defining the value required in terms of pre-existing generic primitives:
--------------- FIRST MISSING NATURAL NUMBER -------------
-- firstGap :: [Int] -> Int
on firstGap(xs)
script p
on |λ|(x)
xs does not contain x
end |λ|
end script
find(p, enumFrom(1))
end firstGap
--------------------------- TEST -------------------------
on run
script test
on |λ|(xs)
showList(xs) & " -> " & (firstGap(xs) as string)
end |λ|
end script
unlines(map(test, ¬
{{1, 2, 0}, {3, 4, -1, 1}, {7, 8, 9, 11, 12}}))
--> {1, 2, 0} -> 3
--> {3, 4, -1, 1} -> 2
--> {7, 8, 9, 11, 12} -> 1
end run
------------------------- GENERIC ------------------------
-- enumFrom :: Enum a => a -> [a]
on enumFrom(x)
script
property v : missing value
on |λ|()
if missing value is not v then
set v to 1 + v
else
set v to x
end if
return v
end |λ|
end script
end enumFrom
-- find :: (a -> Bool) -> Gen [a] -> Maybe a
on find(p, gen)
-- The first match for the predicate p
-- in the generator stream gen, or missing value
-- if no match is found.
set mp to mReturn(p)
set v to gen's |λ|()
repeat until missing value is v or (|λ|(v) of mp)
set v to (|λ|() of gen)
end repeat
v
end find
-- intercalate :: String -> [String] -> String
on intercalate(delim, xs)
set {dlm, my text item delimiters} to ¬
{my text item delimiters, delim}
set s to xs as text
set my text item delimiters to dlm
s
end intercalate
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
-- The list obtained by applying f
-- to each element of xs.
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted into 1st class script wrapper.
if script is class of f then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- showList :: [a] -> String
on showList(xs)
script go
on |λ|(x)
x as string
end |λ|
end script
"{" & intercalate(", ", map(go, xs)) & "}"
end showList
-- unlines :: [String] -> String
on unlines(xs)
-- A single string formed by the intercalation
-- of a list of strings with the newline character.
set {dlm, my text item delimiters} to ¬
{my text item delimiters, linefeed}
set s to xs as text
set my text item delimiters to dlm
s
end unlines
- Output:
{1, 2, 0} -> 3 {3, 4, -1, 1} -> 2 {7, 8, 9, 11, 12} -> 1
Arturo
sets: @[[1 2 0] @[3 4 neg 1 1] [7 8 9 11 12]]
loop sets 's ->
print [
"Set:" s
"-> First missing positive integer:" first select.first 1..∞ 'x -> not? in? x s
]
- Output:
Set: [1 2 0] -> First missing positive integer: 3 Set: [3 4 -1 1] -> First missing positive integer: 2 Set: [7 8 9 11 12] -> First missing positive integer: 1
AutoHotkey
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
# 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
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
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
BQN
FMP ← ⊢(⊑(¬∊˜ )/⊢)1+(↕1+⌈´)
FMP¨ ⟨⟨1,2,0⟩,⟨3,4,¯1,1⟩,⟨7,8,9,11,12⟩⟩
- Output:
⟨ 3 2 1 ⟩
C++
#include <iostream>
#include <unordered_set>
#include <vector>
int FindFirstMissing(const std::vector<int>& r)
{
// put them into an associative container
std::unordered_set us(r.begin(), r.end());
size_t result = 0;
while (us.contains(++result)); // find the first number that isn't there
return (int)result;
}
int main()
{
std::vector<std::vector<int>> nums {{1,2,0}, {3,4,-1,1}, {7,8,9,11,12}};
std::for_each(nums.begin(), nums.end(),
[](auto z){std::cout << FindFirstMissing(z) << " "; });
}
- Output:
3 2 1
CLU
contains = proc [T, U: type] (needle: T, haystack: U) returns (bool)
where T has equal: proctype (T,T) returns (bool),
U has elements: itertype (U) yields (T)
for item: T in U$elements(haystack) do
if item = needle then return(true) end
end
return(false)
end contains
fmp = proc [T: type] (list: T) returns (int)
where T has elements: itertype (T) yields (int)
n: int := 1
while contains[int, T](n, list) do
n := n + 1
end
return(n)
end fmp
start_up = proc ()
si = sequence[int]
ssi = sequence[si]
po: stream := stream$primary_output()
tests: ssi := ssi$[si$[1,2,0], si$[3,4,-1,1], si$[7,8,9,11,12]]
for test: si in ssi$elements(tests) do
for i: int in si$elements(test) do
stream$puts(po, int$unparse(i) || " ")
end
stream$putl(po, "==> " || int$unparse(fmp[si](test)))
end
end start_up
- Output:
1 2 0 ==> 3 3 4 -1 1 ==> 2 7 8 9 11 12 ==> 1
Delphi
Uses the Delphi "TList" object to search the list for missing integers.
var List1: array [0..2] of integer =(1,2,0);
var List2: array [0..3] of integer =(3,4,-1,1);
var List3: array [0..4] of integer =(7,8,9,11,12);
function FindMissingInt(IA: array of integer): integer;
var I,Inx: integer;
var List: TList;
begin
List:=TList.Create;
try
Result:=-1;
for I:=0 to High(IA) do List.Add(Pointer(IA[I]));
for Result:=1 to High(integer) do
begin
Inx:=List.IndexOf(Pointer(Result));
if Inx<0 then exit;
end;
finally List.Free; end;
end;
function GetIntStr(IA: array of integer): string;
var I: integer;
begin
Result:='[';
for I:=0 to High(IA) do
begin
if I>0 then Result:=Result+',';
Result:=Result+Format('%3.0d',[IA[I]]);
end;
Result:=Result+']';
end;
procedure ShowMissingInts(Memo: TMemo);
var S: string;
var M: integer;
begin
S:=GetIntStr(List1);
M:=FindMissingInt(List1);
Memo.Lines.Add(S+' = '+IntToStr(M));
S:=GetIntStr(List2);
M:=FindMissingInt(List2);
Memo.Lines.Add(S+' = '+IntToStr(M));
S:=GetIntStr(List3);
M:=FindMissingInt(List3);
Memo.Lines.Add(S+' = '+IntToStr(M));
end;
- Output:
[ 1, 2, 0] = 3 [ 3, 4, -1, 1] = 2 [ 7, 8, 9, 11, 12] = 1
EasyLang
func missing a[] .
h = 1
repeat
v = 0
for v in a[]
if h = v
break 1
.
.
until v <> h
h += 1
.
return h
.
a[][] = [ [ 1 2 0 ] [ 3 4 -1 1 ] [ 7 8 9 11 12 ] ]
for i to len a[][]
write missing a[i][] & " "
.
- Output:
3 2 1
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 ""
- Output:
3 2 1
Factor
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
FreeBASIC
function is_in( n() as integer, k as uinteger ) as boolean
for i as uinteger = 1 to ubound(n)
if n(i) = k then return true
next i
return false
end function
function fmp( n() as integer ) as integer
dim as uinteger i = 1
while is_in( n(), i )
i+=1
wend
return i
end function
dim as integer a(1 to 3) = {1, 2, 0}
dim as integer b(1 to 4) = {3, 4, -1, 1}
dim as integer c(1 to 5) = {7, 8, 9, 11, 12}
print fmp(a())
print fmp(b())
print fmp(c())
- Output:
3 2 1
Go
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
import Data.List (sort)
task :: Integral a => [a] -> a
task = go . (0 :) . sort . filter (> 0)
where
go [x] = succ x
go (w : xs@(x : _))
| x == succ w = go xs
| otherwise = succ w
main :: IO ()
main =
print $
map
task
[[1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12]]
- Output:
[3,2,1]
Or simply as a filter over an infinite list:
---------- FIRST MISSING POSITIVE NATURAL NUMBER ---------
firstGap :: [Int] -> Int
firstGap xs = head $ filter (`notElem` xs) [1 ..]
--------------------------- TEST -------------------------
main :: IO ()
main =
(putStrLn . unlines) $
fmap
(\xs -> show xs <> " -> " <> (show . firstGap) xs)
[ [1, 2, 0],
[3, 4, -1, 1],
[7, 8, 9, 11, 12]
]
and if xs were large, it could be defined as a set:
import Data.Set (fromList, notMember)
---------- FIRST MISSING POSITIVE NATURAL NUMBER ---------
firstGap :: [Int] -> Int
firstGap xs = head $ filter (`notMember` seen) [1 ..]
where
seen = fromList xs
- Output:
Same output for notElem and notMember versions above:
[1,2,0] -> 3 [3,4,-1,1] -> 2 [7,8,9,11,12] -> 1
J
The first missing positive can be no larger than 1 plus the length of the list, thus:
fmp=: {{ {.y-.~1+i.1+#y }}S:0
(The {{ }} delimiters on definitions, used here, was introduced in J version 9.2)
Example use:
fmp 1 2 0;3 4 _1 1; 7 8 9 11 12
3 2 1
Also, with this approach:
fmp 'abc'
1
JavaScript
(() => {
"use strict";
// ---------- FIRST MISSING NATURAL NUMBER -----------
// firstGap :: [Int] -> Int
const firstGap = xs => {
const seen = new Set(xs);
return filterGen(
x => !seen.has(x)
)(
enumFrom(1)
)
.next()
.value;
};
// ---------------------- TEST -----------------------
// main :: IO ()
const main = () => [
[1, 2, 0],
[3, 4, -1, 1],
[7, 8, 9, 11, 12]
]
.map(xs => `${show(xs)} -> ${firstGap(xs)}`)
.join("\n");
// --------------------- GENERIC ---------------------
// enumFrom :: Int -> [Int]
const enumFrom = function* (x) {
// A non-finite succession of
// integers, starting with n.
let v = x;
while (true) {
yield v;
v = 1 + v;
}
};
// filterGen :: (a -> Bool) -> Gen [a] -> Gen [a]
const filterGen = p =>
// A stream of values which are drawn
// from a generator, and satisfy p.
xs => {
const go = function* () {
let x = xs.next();
while (!x.done) {
const v = x.value;
if (p(v)) {
yield v;
}
x = xs.next();
}
};
return go(xs);
};
// show :: a -> String
const show = x => JSON.stringify(x);
// MAIN ---
return main();
})();
- Output:
[1,2,0] -> 3 [3,4,-1,1] -> 2 [7,8,9,11,12] -> 1
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
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
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
#!/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
with javascript_semantics 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
Python
'''First missing natural number'''
from itertools import count
# firstGap :: [Int] -> Int
def firstGap(xs):
'''First natural number not found in xs'''
return next(x for x in count(1) if x not in xs)
# ------------------------- TEST -------------------------
# main :: IO ()
def main():
'''First missing natural number in each list'''
print('\n'.join([
f'{repr(xs)} -> {firstGap(xs)}' for xs in [
[1, 2, 0],
[3, 4, -1, 1],
[7, 8, 9, 11, 12]
]
]))
# MAIN ---
if __name__ == '__main__':
main()
- Output:
[1, 2, 0] -> 3 [3, 4, -1, 1] -> 2 [7, 8, 9, 11, 12] -> 1
QBasic
DECLARE FUNCTION isin (n(), k)
DECLARE FUNCTION fmp (n())
DIM a(3)
FOR x = 1 TO UBOUND(a): READ a(x): NEXT x
DIM b(4)
FOR x = 1 TO UBOUND(b): READ b(x): NEXT x
DIM c(5)
FOR x = 1 TO UBOUND(c): READ c(x): NEXT x
PRINT fmp(a())
PRINT fmp(b())
PRINT fmp(c())
Sleep
END
DATA 1,2,0
DATA 3,4,-1,1
DATA 7,8,9,11,12
FUNCTION fmp (n())
j = 1
WHILE isin(n(), j)
j = j + 1
WEND
fmp = j
END FUNCTION
FUNCTION isin (n(), k)
FOR i = LBOUND(n) TO UBOUND(n)
IF n(i) = k THEN isin = 1
NEXT i
END FUNCTION
- Output:
3 2 1
Quackery
Using a bitmap as a set
Treat a number (BigInt) as a set of integers. Add the positive integers to the set, then find the first positive integer not in the set.
[ 0 0 rot
witheach
[ dup 0 > iff
[ bit | ]
else drop ]
[ dip 1+
1 >> dup 1 &
0 = until ]
drop ] is task ( [ --> n )
' [ [ 1 2 0 ] [ 3 4 -1 1 ] [ 7 8 9 11 12 ] ]
witheach [ task echo sp ]
- Output:
3 2 1
Using filtering and sorting
Filter out the non-positive integers, and then non-unique elements (after adding zero).
uniquewith
is defined at Remove duplicate elements#Quackery and conveniently sorts the nest.
Then hunt for the first item which does not have the same value as its index. If they all have the same values as their indices, the missing integer is the same as the size of the processed nest.
[ [] swap
witheach
[ dup 0 > iff
join
else drop ]
0 join
uniquewith >
dup size swap
witheach
[ i^ != if
[ drop i^
conclude ] ] ] is task ( [ --> n )
' [ [ 1 2 0 ] [ 3 4 -1 1 ] [ 7 8 9 11 12 ] ]
witheach [ task echo sp ]
- Output:
3 2 1
Brute force
Search for each integer. The largest the missing integer can be is one more than the number of items in the nest.
[ dup size
dup 1+ unrot
times
[ i^ 1+
over find
over found not if
[ dip
[ drop i^ 1+ ]
conclude ] ]
drop ] is task ( [ --> n )
' [ [ 1 2 0 ] [ 3 4 -1 1 ] [ 7 8 9 11 12 ] ]
witheach [ task echo sp ]
- Output:
3 2 1
Raku
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
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
nums = [[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 n = 1 to len(nums)
see "the smallest missing positive integer for "
? (arrayToStr(nums[n]) + ": " + fmp(nums[n]))
next
func fmp(ary)
if len(ary) > 0
for m = 1 to max(ary) + 1
if find(ary, m) < 1 return m ok
next ok return 1
func arrayToStr(ary)
res = "[" s = ","
for n = 1 to len(ary)
if n = len(ary) s = "" ok
res += "" + ary[n] + s
next return res + "]"
- 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 the smallest missing positive integer for [1,2,3,4,5]: 6 the smallest missing positive integer for [-6,-5,-2,-1]: 1 the smallest missing positive integer for [5,-5]: 1 the smallest missing positive integer for [-2]: 1 the smallest missing positive integer for [1]: 2 the smallest missing positive integer for []: 1
RPL
≪ 1 WHILE DUP2 POS REPEAT 1 + END SWAP DROP ≫ 'FINDF' STO
{ { 1 2 0 } { 3 4 -1 1 } { 7 8 9 11 12 } } 1 ≪ FINDF ≫ DOLIST
- Output:
1: { 3 2 1 }
Ruby
nums = [1,2,0], [3,4,-1,1], [7,8,9,11,12]
puts nums.map{|ar|(1..).find{|candidate| !ar.include?(candidate) }}.join(", ")
- Output:
3, 2, 1
Sidef
[[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], []].each {|arr|
var s = Set(arr...)
say (arr, " ==> ", 1..Inf -> first {|k| !s.has(k) })
}
- 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
True BASIC
FUNCTION isin (n(), k)
FOR i = LBOUND(n) TO UBOUND(n)
IF n(i) = k THEN LET isin = 1
NEXT i
END FUNCTION
FUNCTION fmp (n())
LET j = 1
DO WHILE isin(n(), j) = 1
LET j = j + 1
LOOP
LET fmp = j
END FUNCTION
DIM a(3)
FOR x = 1 TO UBOUND(a)
READ a(x)
NEXT x
DIM b(4)
FOR x = 1 TO UBOUND(b)
READ b(x)
NEXT x
DIM c(5)
FOR x = 1 TO UBOUND(c)
READ c(x)
NEXT x
PRINT fmp(a())
PRINT fmp(b())
PRINT fmp(c())
DATA 1,2,0
DATA 3,4,-1,1
DATA 7,8,9,11,12
END
V (Vlang)
fn first_missing_positive(a []int) int {
mut b := []int{}
for e in a {
if e > 0 {
b << e
}
}
b.sort<int>()
le := b.len
if le == 0 || b[0] > 1 {
return 1
}
for i in 1..le {
if b[i]-b[i-1] > 1 {
return b[i-1] + 1
}
}
return b[le-1] + 1
}
fn main() {
println("The first missing positive integers for the following arrays are:\n")
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 {
println("$a -> ${first_missing_positive(a)}")
}
}
- Output:
Same as go entry
Wren
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
XPL0
proc ShowMissing(Arr, Len);
int Arr, Len, N, N0, I;
[N:= 1;
repeat N0:= N;
for I:= 0 to Len-1 do
if Arr(I) = N then N:= N+1;
until N = N0;
IntOut(0, N); ChOut(0, ^ );
];
int I, Nums;
[for I:= 0 to 2 do
[Nums:= [[1,2,0], [3,4,-1,1], [7,8,9,11,12], [0]];
ShowMissing( Nums(I), (Nums(I+1)-Nums(I))/4 );
];
]
- Output:
3 2 1