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

Nekomata + -1, 4 bytes

ŇPᵖf

Attempt This Online!

The flag -1 set the interpreter to FirstValue mode, which prints the first possible result.

Ň        Non-deterministically choose an natural number
 P       that is positive
  ᵖ      and such that
   f     the input doesn't contain this number

---

Nekomata v0.1.0.0 + -1, 6 bytes

ℕPᵖ{-Z

This is the original answer in an old version of Nekomata. Some symbols are changed in newer versions.

ℕ        Non-deterministically choose an natural number
 P       that is positive
  ᵖ{     and such that
    -Z   it minus the input doesn't contain any zero

Answer 2

Nibbles, 3 2 bytes (4 nibbles)

/-,~

I somehow didn't expect that fold-ing over an infinite list, starting from infinity (the right-hand end) would work, but it does.

/-,~    # full function
/-,~$$  # (with implicit arguments shown):
 -      # remove
    $   #   elements of the input list 
        # from
  ,~    #   the infinite list of positive integers
/       # now fold over this infinite list from the right
     $  # each time returning the left-hand argument
  -     # (so, finally, returning the first (left-most) element)

Answer 3

Zsh, 21 bytes

seq inf|grep -xvm1 $1

Attempt This Online!

• seq inf: list of all positive integers
• grep: filter those for
  • $1: any of the lines in the input
  • -v: inverted match (i.e., it must not match any of the input items)
  • -x: match whole lines, not substrings
  • -m1: output only the first matching line

Answer 4

flax, 7 bytes

∵µḟκ→A∴

Attempt This Online!

Explained

∵µḟκ→A∴
∵        ⊳ min of
   κ→A∴  ⊳ range(1, abs(max(input)) + 2)
  ḟ      ⊳ set diff with input

Answer 5

JavaScript (ES6), 33 bytes

a=>a.reduce(m=>m+a.includes(m),1)

Try it online!

Answer 6

Brachylog, 7 6 5 bytes

ℕ₁≜¬∈

Try it online!

-1 stealing Fatalize's solution to the dupe target--note that my accepted reverted golf suggestion fails on the empty list. Whoops

Reversed I/O.

ℕ₁       The output is a positive integer.
  ≜      Try every value for it until one
   ¬∈    isn't in the input.

Answer 7

Jelly, 4 bytes

1ḟ1#

Try it online!

  1#    Find the first integer
1       starting from 1
 ḟ      which is not empty with elements of the list filtered out.

Answer 8

x86-64 machine code, 13 bytes

31 C0 FF C0 89 F1 57 F2 AF 5F 74 F6 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the address of an array of 32-bit integers in RDI and its length in ESI, and returns a 32-bit integer in EAX.

In assembly:

f:  xor eax, eax    # Set EAX to 0.
r:  inc eax         # Increase EAX by 1.
    mov ecx, esi    # Set ECX to the length.
    push rdi        # Save the value of RDI onto the stack.
    repne scasd     # Compare EAX and the value at address RDI,
                    #  advancing the pointer and counting down ECX,
                    #  and repeat as long as the result is unequal and ECX≠0.
    pop rdi         # Restore the value of RDI from the stack.
    je r            # Jump back if the last comparison result was equal.
    ret             # Return.

Answer 9

Python 3, 38 bytes

f=lambda a,i=1:i in a and f(a,i+1)or i

A recursive function that accepts the list and returns the first missing positive integer.

Try it online!

Answer 10

Pyth, 3 bytes

-#Q

Try it online!

This challenge is extremely well-suited for Pyth. Let's go through it step by step:

• #: This is the filter function. The predicate function that is used as the filter is -TQ, where T is the variable representing the values being filtered over. No explicit input is given. When no input is given, # outputs the first positive integer for which the predicate function gives a truthy output.

• -: This is subtraction function. It is called on T, a positive integer, and Q, the input list for the program. When - is called with an integer followed by a list, it returns a singleton list containing the integer, if the integer is absent from the list, or else an empty list.

Here's an equivalent Python program to the above Pyth program, to hopefully make it clearer what's going on.

import ast
Q = ast.literal_eval(input())
T = 1
while True:
    subtract_in = [T]
    subtract_out = [elem for elem in subtract_in if elem not in Q]
    if subtract_out:
        print(T)
        break
    T += 1

Try it online!

Answer 11

Vyxal,  6  5  4 bytes

?F)ṅ

Try it Online!

-2 thanks to @lyxal

Explanation

?F)ṅ  # Implicit input
  )ṅ  # First integer where:
?F    #  Remove elements from the input which are in this number
      #  (i.e. is the number not in the input)

Answer 12

Haskell + hgl, 10 bytes

he<df[1..]

Attempt This Online!

My first hgl answer. Returns the first element of the "set" difference of the input from the positive integers.

Potential useful additions (or that I couldn't find):

• a two or three byte alias for [1..]
• find the first item in the list matching a predicate ((hd<)<fl)
• find the first positive integer matching a predicate (a special-cased combination of the above two; like Jelly's #)
• (I didn't use it in the code itself, but in the footer), read Maybe there's some fancy equivalent in P.Parse, but I couldn't find it

I'd like to set up an instance of hoogle for hgl - it would make searching for things easier.

Answer 13

Zsh, 31 bytes

Unlike pxeger's answer, no external programs, just pure shell constructs.

<<<${${${:-{1..1$#}}:|argv}[1]}

Try it online!

       ${:-{1..1$#}}             # List from 1 to a number bigger than the length of the list.
                                 # It's shorter to prepend a "1" than to add 1.
     ${             :|argv}      # :| set difference with the list
<<<${                      [1]}  # print the first result

Answer 14

R, 31 bytes

\(x,y=seq(c(1,x)))y[!y%in%x][1]

Attempt This Online!

Answer 15

R, 27 bytes

\(x){while(T%in%x)T=T+1;+T}

Attempt This Online!

Naive approach. For a clever one (and currently longer) see @Dominic van Essen's answer.

Answer 16

Haskell, 30 bytes

f a=filter(`notElem`a)[1..]!!0

Try it online!

Answer 17

Jelly, 6 bytes

ṀŻ‘ḟ³Ṃ

Try it online

Explanation

ṀŻ‘ḟ³Ṃ  #                  | [-1, 0, 1, 4]
Ṁ       # Maximum          | 4
 Ż      # Range from 0     | [0, 1, 2, 3, 4]
  ‘     # Increment        | [1, 2, 3, 4, 5]
   ḟ    # Filter out items |
    ³   # In the input     | [2, 3, 5]
     Ṃ  # Minimum          | 2

Answer 18

Perl 5 -ap, 20 bytes

1while++$i~~@F;$_=$i

Try it online!

Answer 19

Japt, 6 bytes

@øX}f1

Try it

@øX}f
@  }f  # first positive integer where the following is false:
 øX    # the array contains the integer

Answer 20

K (ngn/k), 14 bytes

{(~^x?)(1+)/1}

Try it online!

Sets up a while-reduce, seeded with 1, that proceeds to the next iteration (adding one) if the current value is already present in the original input.

Answer 21

Desmos, 70 65 bytes

j=join(x,0)
l=[isgn(i-j)^2.minfori=[1...j.max+1]]
f(x)=l[l>0].min

Try it on Desmos!

-5 bytes thanks to Aiden Chow.

Answer 22

PowerShell Core, 22 bytes

for(;++$i-in$args){}$i

Try it online!

Takes the input array using splatting, returns an integer

Answer 23

Julia 1.0, 26 bytes

>(x,i=1)=i∈x ? x>i+1 : i

Try it online!

Answer 24

Julia, 36 33 bytes

~x=argmax(!in(x),1:1+max(0,x...))

Attempt This Online!

Returns the first index of range [1,max+1] that isn't in the input. To accommodate the empty list, the input is padded with 0.

• -3 bytes thanks to MarcMush: replace findfirst with argmax
• -2 bytes thanks to MarcMush: replace0∪x... with 0,x...

Answer 25

Excel, 61 bytes

=@LET(a,A1#,b,SEQUENCE(MAX(a,-a)+1),SORTBY(b,XMATCH(b,a),-1))

Input is spilled array A1#.

Answer 26

MATL, 6 bytes

`@Gm}@

Try it at MATL Online! Or verify all test cases.

Explanation

`      % Do...while
  @    %   Push interation index, 1-based
  G    %   Push input
  m    %   Ismember. Gives true or false
}      % Finally (i.e. execeute when exiting the loop)
  @    %   Push iteration index
       % End (implicit). A new iteration is run if top of the stack is true
       % Display (implicit)

Answer 27

Charcoal, 13 10 bytes

Ｉ⌊⁻…·¹⊕Ｌθθ

Try it online! Link is to verbose version of code. Explanation: Now a port of @GammaFunction's jq answer.

   …·       Inclusive range from
     ¹      Literal integer `1` to
        θ   Input list
       Ｌ    Take the length
      ⊕     Incremented
  ⁻             Set difference with
         θ  Input list
 ⌊          Take the minimum
Ｉ           Cast to string
            Implicitly print

Would have been 6 bytes if the input had been guaranteed to be a nonempty list of positive integers:

Ｉ⌊⁻⊕θθ

Try it online! Link is to verbose version of code. Explanation:

    θ   Input list
   ⊕    Vectorised increment
  ⁻     Set difference with
     θ  Input list
 ⌊      Take the minimum
Ｉ       Cast to string
        Implicitly print

Answer 28

05AB1E, 5 4 bytes

∞IKн

Try it online!

-1 thanks to @KevinCruijssen

Explanation

∞IKн  # Implicit input
∞     # Push the infinite list [1, 2, 3, ...]
 IK   # Remove the elements of the input
   н  # First item

Old:

∞å0k>  # Implicit input
∞      # For each number in the infinite list [1, 2, 3, ...]
 å     # Is it in the input?
  0k   # Get the index of the first 0 (0-indexed)
    >  # And increment it to make it 1-indexed

Answer 29

Japt, 6 bytes

@øX}f1

Try it

@øX}f1     :Implicit input of array U
@          :Function taking an integer X as argument
 øX        :  Does U contain X
   }       :End function
    f1     :Get the first integer >=1 that returns false

Answer 30

Python 3 NumPy, 31 bytes

lambda a:min({1,*a+(a>0)}-{*a})

Try it online!

Expects a numpy array.

How?

Returns 1 if that's not in a and otherwise the smallest successor of a positive number in a that's not in a.