Find first missing positive: Difference between revisions
Content added Content deleted
(→{{header|JavaScript}}: Switched from `Array.includes` to `Set.has`) |
(→{{header|Haskell}}: Added a variant in which the predicate is defined over a set, rather than a list.) |
||
Line 426: | Line 426: | ||
[7, 8, 9, 11, 12] |
[7, 8, 9, 11, 12] |
||
]</lang> |
]</lang> |
||
and if xs were large, it could be defined as a set: |
|||
<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</lang> |
|||
{{Out}} |
{{Out}} |
||
Same output for '''notElem''' and '''notMember''' versions above: |
|||
<pre>[1,2,0] -> 3 |
<pre>[1,2,0] -> 3 |
||
[3,4,-1,1] -> 2 |
[3,4,-1,1] -> 2 |