Shortest Code to Find the Smallest Missing Positive Integer

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>

• Can the array be assumed not to contain duplicates? Feb 26 at 13:02
• @UnrelatedString duplicates are allowed Feb 26 at 13:03
• 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. Feb 26 at 14:02
• 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). Feb 26 at 14:09
• @chunes yes, while they are fixed ranges, most answers can be trivially ported back and forth. that is our requirement for dupes Feb 27 at 1:40

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

• Cool language! Glad to see someone's made a backtracking stack language Feb 26 at 12:59
• How does this code guarantee that you get the smallest such number? Feb 28 at 22:50
• @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 ℕ is always the smallest one. Feb 28 at 23:56

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

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)


• nibbles is written in Haskell, which is pretty good about lazy lists
– Jo King
Mar 5 at 1:54

flax, 7 bytes

∵µḟκ→A∴


Attempt This Online!

Explained

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

• 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 Feb 26 at 13:25
• +1 Nice answer! Feb 26 at 15:44

JavaScript (ES6), 33 bytes

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


Try it online!

• 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) Feb 27 at 16:17
• @Fhuvi Thank you! Posted. :-) Feb 27 at 17:34

Brachylog, 76 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.


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.


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.

• 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. Feb 27 at 23:25
• 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. Feb 27 at 23:27

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!

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!

• you seem to be rather good at pyth :P Feb 27 at 20:54
• @mathcat Gee, I wonder why that might be Feb 27 at 20:54

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)

• c automatically swaps arguments if one is a list and one is a number/string, so the $ isn't needed Feb 26 at 12:50 • Try it Online! for 4 bytes Feb 26 at 12:53 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  R, 31 bytes \(x,y=seq(c(1,x)))y[!y%in%x][1]  Attempt This Online! 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. Haskell, 30 bytes f a=filter(notElema)[1..]!!0  Try it online! 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  Perl 5 -ap, 20 bytes 1while++$i~~@F;$_=$i


Try it online!

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.

Japt, 6 bytes

@øX}f1


Try it

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

• Feb 26 at 15:44
• The output should never be 0 - it says positive integer, not non-negative. Feb 26 at 16:00
• @TheThonnu Oops will fix, now it's exactly the same as Shaggy's lol Feb 26 at 16:01

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.

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.

• 65 bytes Feb 26 at 23:03

PowerShell Core, 22 bytes

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


Try it online!

Takes the input array using splatting, returns an integer

Julia 1.0, 26 bytes

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


Try it online!

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...
• -1 byte: max(0,x...) Mar 5 at 19:27
• here too, argmax can save some bytes Jun 16 at 18:38

Excel, 61 bytes

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


Input is spilled array A1#.

• 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]. Feb 27 at 12:38
• @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))). Feb 27 at 15:04

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)


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


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


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


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.