Shortest Code to Find the Smallest Missing Positive Integer

Question

Description

Given an unsorted array of integers, find the smallest positive integer that does not appear in the array. Your task is to write the shortest code possible to solve this problem.

Input

A non-empty or empty array of integers, where the integers may be negative, zero, or positive.

Output

The smallest positive integer that does not appear in the array.

Test cases

Input: [1, 2, 3]
Output: 4

Input: [3, 4, -1, 1]
Output: 2

Input: [7, 8, 9, 11, 12]
Output: 1

Input: [-5, -4, -3, -2, -1, 0, 1, 2, 3, 5, 7, 10]
Output: 4

Input: []
Output: 1

Input: [-1, -4, -7]
Output: 1

Scoring criteria: Your score is the number of bytes in your code, as counted by the bytecount tool. The code with the smallest number of bytes wins. In the case of a tie, the earlier submission wins.

var QUESTION_ID=258335,OVERRIDE_USER=117038;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

JavaScript (Node.js), 35 34 bytes

a=>(g=i=>a.includes(++i)?g(i):i)``

Try it online!

Port of Jonathan Allan's Python answer.

-1 thanks to @Shaggy

Answer 2

Arturo, 26 bytes

$[a][min--@1..+1max a++1a]

Try it

$[a][              ; a function taking an argument a
    min            ; the minimum element of
    --             ; the set difference of
    @              ; the array of
    1..            ; the range from one to
    +1             ; one plus
    max            ; the maximum element of
    a++1           ; a with 1 appended (for empty input)
    a              ; and a -- the second argument to set difference
]                  ; end function

Answer 3

Python 3, 38 bytes

lambda a:[*{*range(len(a)+2)}-{*a}][1]

Uses set differences to get the missing number after removing negative numbers.

Try it online!

-22 bytes by using {} to make set. And no need to check if positive

Answer 4

TI-BASIC, 17 bytes

1
While sum(Ans=L1
Ans+1
End
Ans

We first put 1 in Ans for the first pass of the loop. Because we're using the While loop the condition will be checked first before the loop runs and 1 will return if it's not in the list. The condition returns a list with the operation against each element so for example a list {1,2,3 will turn to {1,0,0 then sum to 1 and pass the condition allowing the loop to continue. the loop itself then can track the counter in Ans instead of needing to store to a variable. After the loop finishes we use the implicit final line Disp to display the value in Ans.

Answer 5

Swift, 46 bytes

var l={(a:[_])in(1...).first{!a.contains($0)}}

The type signature [_] tells the compiler to infer the Array's Element type via type inference (possible thanks to the 1... range).

Answer 6

jq, 26 bytes

[range(1;length+2)]-.|.[0]

Try it online!

Input:	.	[]	[5,1,0,1]
Need to add 2 because range isn't inclusive	length+2	2	6
[] makes it a list	[range(1;length+2)]	[1]	[1,2,3,4,5]
LIST - LIST is set difference	[range(1;length+2)]-.	[1]	[2,3,4]
Select first element	[range(1;length+2)]-.|.[0]	1	2

Answer 7

Python, 66 bytes

lambda l:min(i for i in range(1,abs(max(l or[1]))+2)if i not in l)

Attempt This Online!

Whython, 57 bytes

lambda l:min(i for i in range(1,max(l)+2)if i not in l)?1

Attempt This Online!

Whython's ? command catches the error of either from either max or min.

Answer 8

Haskell, 31 bytes

import Data.List
head.([1..]\\)

A port of pxeger's answer using only the standard library. I quite like the approach using Haskell's lazyness.

Answer 9

MathGolf, 9 bytes

1▐╙)╒\-├Þ

Try it online.

Explanation:

1▐         # Append a 1 to the (implicit) input-list
  ╙        # Pop and push its maximum
   )       # Increase it by 1
    ╒      # Pop and push a list in the range [1,max+1)
     \     # Swap so the (implicit) input-list is at the top of the stack
      -    # Remove all those values from the ranged list
       ├   # Push its first item (without popping unfortunately)
        Þ  # Only keep the top item of the stack
           # (after which the entire stack is output implicitly as result)

Answer 10

Raku, 19 bytes

{first *∉$_,1..*}

Try it online!

Returns the first element of the lazy sequence of positive integers 1 .. * such that the number is not an element of the input list: * ∉ $_.

Answer 11

Wolfram Language (Mathematica), 25 bytes

1//.x_/;#~MemberQ~x:>x+1&

Try it online! (verifies all test cases) Exact same implementation as this earlier answer of mine, except testing whether the temporary variable is a member of the input rather than divides the input. (Has the same limitation as that answer, that Mathematica's default recursion limit is 65536.)

Answer 12

PHP -F, 35 bytes

for(;in_array(++$i,$argn););echo$i;

Try it online!

I did something a bit unusual here, as command-line arguments give a string, and question says we are provided an array, is to decode the string off the byte count. If you think this is wrong I will include it in the count

Answer 13

Java 8 (OpenJDK 8), 53 bytes

Solution using inline stream :

l->l.stream().sorted().reduce(1,(a,b)->a<b|b<1?a:b+1)

Try it online!

Answer 14

Pascal, 160 bytes

This function requires a processor compliant to at least ISO standard 7185 “Standard Pascal”, level 1. Note, in Pascal it is not possible to specify “empty arrays”, therefore the fifth test case is not applicable.

function f(x:array[m..n:integer]of integer):integer;var s:set of integer;i:integer;begin s:=[];for i:=m to n do s:=s+[x[i]];i:=1;while i in s do i:=i+1;f:=i end 

Ungolfed (Extended Pascal, ISO standard 10206, level 1):

type
    natural = 1..maxInt;
    integerWithoutMaxint = -maxInt..pred(maxInt);

function naturalSupremum(
        { This is a “conformant-array parameter”. It permits us writing a
          generic routine without specifying the array’s size in advance. }
        sample: array[indexMinimum..indexMaximum: integer] of integerWithoutMaxint
        { The `array` may not contain the value `maxInt`, hence the restriction
          to `integerWithoutMaxint`. Otherwise the `result := result + 1;` will
          overflow if all values in the interval [1, maxInt] are present. }
    ): natural;
var
    range: set of integer value [];
    i: type of indexMinimum;
    result: natural value 1;
begin
    { transform ordered list to “unordered” `set` -------------------- }
    for i := indexMinimum to indexMaximum do
    begin
        range := range + [sample[i]];
    end;
    
    { analyze step: find first `natural` not part of set ------------- }
    while result in range do
    begin
        result := result + 1;
    end;
    
    { In Pascal there must be exactly _one_ assignment to the
      implicit result variable bearing the same name as the function. }
    naturalSupremum := result
end;

Answer 15

Python 3 REPL, 52 bytes

next(i for i in range(1,max(_+[0])+2) if i not in _)

Returns the first integer in the range [1, (maximum of input and 0) + 2), that is not present in the input.

Replacing max(_+[0])+2 with 10**9 saves 7 bytes, but assumes the input it short enough.

Using the REPL so we can take the input as variable _.

Answer 16

BQN, 17 bytes

{1+⊑/¬(«↕2+≠𝕩)∊𝕩}

Try it online!

Explanation

{1+⊑/¬(«↕2+≠𝕩)∊𝕩}
{     (      )∊𝕩} 1. Is the input in...
      ( ↕    )    2a. the natural numbers from 0 to...
      (  2+≠𝕩)    2b. the length of the input plus 2...
      («     )    2c. left-shifted (to get rid of 0)
{    ¬          } 3. in -> not in
    /             4. Which indices are true
 1+⊑              5. Take the first (add 1 due to 0-indexing)

Answer 17

Python 3, 41 bytes

lambda x:min({1,*range(max(x)+2)}-{0,*x})

Try it online!

A non-recursive approach that works by generating the set of all possible numbers it could be (and 0), removing the ones it can't be, and selecting the smallest remaining number.

Alternatively, range(1,max(x)+2) and {*x}, but that looks less fun :>

Answer 18

Factor + lists.lazy math.unicode, 36 bytes

[ 1 lfrom [ ∌ ] with lfilter car ]

Try it online!

• 1 lfrom the natural numbers
• [ ∌ ] with lfilter select the numbers that are not in the input
• car get the first one

Answer 19

C (gcc), 58 57 bytes

1 byte saved thanks to @ceilingcat!

i;c;f(a,k)int*a;{for(i=0,c=1;i<k;i=c-a[i]?i+1:!c++);a=c;}

Try it online!

Takes as input a pointer to the start of an integer range, and the number if integers in said range.

I almost had 44 bytes with the beautiful-looking recursive i;f(a,k)int*a;{a=k?i+=(i=f(a,--k))==a[k]:1;}, but this unfortunately doesn't work on specific unsorted arrays, such as [1, 4, 3, 2]. :(

i=0,c=1 feels clunky and long but I don't see a way to eliminate it.

Explanation

Abusing K&R C implementation for saving lots of bytes:

• i;c; instead of int i,c; for some global variables
• f(a,k)int*a; instead of int f(int*a,int k)
• c-a[i] instead of c!=a[i]
• i=...?i+1:!c++ instead of if(...)i++;else i=0,c++;
• a=c; instead of return c;

Answer 20

Rust, 39 bytes

|v:Vec<_>|(1..).find(|i|!v.contains(i))

Attempt This Online!

Now the thing with this solution is it returns Some(n); not sure if that's allowed. So here is a solution which returns an integer instead:

Rust, 48 bytes

|v:Vec<_>|(1..).find(|i|!v.contains(i)).unwrap()

Attempt This Online!

Answer 21

Thunno 2, 3 bytes

ƘƇ~

Try it online!

Explanation

ƘƇ~  # Implicit input
Ƙ    # First integer where:
 Ƈ~  #  Not in input
     # Implicit output

Answer 22

Scala, 61 bytes

Port of @Jonathan Allan's Python code in Scala.

---

Golfed version. Try it online!

def f(a:Seq[Int],i:Int=1):Int=if(a.contains(i))f(a,i+1)else i