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>

• Unrelated String: Can the array be assumed not to contain duplicates?
• aitzazisstuffed: @UnrelatedString duplicates are allowed
• aitzazisstuffed: sorry but its not at all related, its asking for missing integer from 1-9 in an answer, while I am asking for smallest missing positive integer in an array.
• chunes: In my opinion, this question is neither a dupe of Minimum excluded number nor Output the missing number because they are both looking at only fixed ranges (0-9 and 0-20).
• Seggan: @chunes yes, while they are fixed ranges, most answers can be trivially ported back and forth. that is our requirement for dupes

Answer 1

Nekomata + -1, 4 bytes

ŇPpf

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
 p and such that
 f the input doesn't contain this number

---

Nekomata v0.1.0.0 + -1, 6 bytes

NPp{-Z

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

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

• Unrelated String: Cool language! Glad to see someone's made a backtracking stack language
• Dan Staley: How does this code guarantee that you get the smallest such number?
• alephalpha: @DanStaley Non-determinism doesn't mean that the choice is random, but means that there are multiple possible values. The interpreter chooses the correct value via backtracking. The first value for N is always the smallest one.

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)

enter image description here

• Jo King: nibbles is written in Haskell, which is pretty good about lazy lists
• noodle person: I really like that trick of folding over the list and returning the implicit argument as a way of getting the first item of a list lol, seems like it might come in handy somewhere else as well

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!

enter image description here

Explained

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

• aitzazisstuffed: The test case says that if all numbers in index are negative then output must be 1, whilst your code gives error when all elements are negative

Answer 5

JavaScript (ES6), 33 bytes

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

Try it online!

• Fhuvi: This is really clever! I had a hard time understanding why it works, but now it's ok :) You could also post nearly the same solution to this problem : codegolf.stackexchange.com/questions/38325/… (and beat all of its previous JS answers)
• Arnauld: @Fhuvi Thank you! Posted. :-)

Answer 6

Brachylog, (削除) 7 (削除ここまで) (削除) 6 (削除ここまで) 5 bytes

N1≜¬∈

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.

N1 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.

• Peter Cordes: My first thought was a (potentially huge) bitset, using bts to construct it, and not+bsf to scan it for missing numbers. (Or init to all-ones, btr construct from the array, bsf to find the first uncleared bit.) That would have O(N) run time instead of O(N^2), but would require more code. I'm curious how much more. rep scasd gets the linear search done very compactly.
• Peter Cordes: 32-bit mode could save a byte here, allowing 1-byte inc eax. (The calling convention wouldn't be one of the standard C conventions for 32-bit mode, but that's allowed for asm / machine code.) push/pop instead of 2-byte mov is break-even in 32-bit mode, or a win vs. 3-byte mov r64, r64 in 64-bit mode, so that's good whether you use push/pop to save/restore here or to copy a register, e.g. if you took in dummy=EDI, len=ESI, and pointer=RDX). I don't see any savings.

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!

• math scat: you seem to be rather good at pyth :P
• izzyg: @mathcat Gee, I wonder why that might be

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)

• lyxal: c automatically swaps arguments if one is a list and one is a number/string, so the $ isn't needed
• lyxal: Try it Online! for 4 bytes

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.

• Wheat Wizard: I only saw this a year late, but I'm very glad to see someone using hgl! The nN is the alias for [1..] you were looking for, it was added in October 2021. Finding the first element of a list matching a predicate is g1, however that was added after this answer was written albeit indpendently. The other things don't exist at the moment. Thanks for the suggestions.

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

ṀŻ‘ḟ3Ṃ

Try it online

Explanation

ṀŻ‘ḟ3Ṃ # | [-1, 0, 1, 4]
Ṁ # Maximum | 4
 Ż # Range from 0 | [0, 1, 2, 3, 4]
 ‘ # Increment | [1, 2, 3, 4, 5]
 ḟ # Filter out items |
 3 # 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

• Shaggy: Ninjaed!
• The Thonnu: The output should never be 0 - it says positive integer, not non-negative.
• noodle person: @TheThonnu Oops will fix, now it's exactly the same as Shaggy's lol

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.

• Aiden Chow: 65 bytes

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

• MarcMush: -1 byte: max(0,x...)
• MarcMush: here too, argmax can save some bytes

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#.

• Engineer Toast: 48 byte solution that assumes values are input individually into the cells in column A but you could save a byte by replacing ,A:A,0) with just ,A#,0) if you did assume that: =MIN(IFERROR(""&MATCH(ROW(A:A),A:A,0),ROW(A:A))). Don't change ROW(A:A) to ROW(A#), though. That would only work if the size of the input is larger than the first integer that was missing and that's not the case for [1, 2, 3].
• Jos Woolley: @EngineerToast Great stuff! You should post that! I guess we can make it 44 bytes, viz =MIN(IFNA(""&MATCH(ROW(A:A),A:A,),ROW(A:A))).

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

I⌊−...·1⊕Lθθ

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

 ...· Inclusive range from
 1 Literal integer `1` to
 θ Input list
 L Take the length
 ⊕ Incremented
 − Set difference with
 θ Input list
 ⌊ Take the minimum
I Cast to string
 Implicitly print

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

I⌊−⊕θθ

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

 θ Input list
 ⊕ Vectorised increment
 − Set difference with
 θ Input list
 ⌊ Take the minimum
I 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

• Kevin Cruijssen: 4 bytes: ∞IKн

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.