27
\$\begingroup\$

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>

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

52 Answers 52

1
2
1
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ 34 bytes \$\endgroup\$
    – Shaggy
    Commented Feb 27, 2023 at 9:32
  • \$\begingroup\$ @Shaggy thanks, updated \$\endgroup\$
    – The Thonnu
    Commented Feb 27, 2023 at 14:32
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ Pretty sure this works just fine for 38 bytes: lambda a:[*{*range(len(a)+2)}-{*a}][1] \$\endgroup\$
    – Aiden Chow
    Commented Mar 4, 2023 at 22:03
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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: * ∉ $_.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ MemberQ->!FreeQ \$\endgroup\$
    – att
    Commented Jun 16, 2023 at 1:10
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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;
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
3
  • 1
    \$\begingroup\$ This looks like it's intended to take input as a variable. You should check out our allowed input methods. You could make this a function by adding lambda x: to the front, \$\endgroup\$
    – Wheat Wizard
    Commented Feb 28, 2023 at 12:41
  • \$\begingroup\$ @WheatWizard According to codegolf.meta.stackexchange.com/a/8580/117110 I can take input as "the value of the last expression". Can I replace x with _ and be done? \$\endgroup\$
    – AI0867
    Commented Feb 28, 2023 at 12:57
  • \$\begingroup\$ That only works int the repl, which is fine, but it's not an answer in Python 3, it's an answer in Python 3 repl. So you can replace x with _, but you should modify the header to be clear. \$\endgroup\$
    – Wheat Wizard
    Commented Feb 28, 2023 at 13:02
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ It looks less fun but wouldn't it be shorter (making sure to replace max(x) with len(x) to account for the empty list)? Like this is 39 bytes: lambda x:min({*range(1,len(x)+2)}-{*x}) \$\endgroup\$
    – Aiden Chow
    Commented Mar 4, 2023 at 22:10
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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;
\$\endgroup\$
1
  • \$\begingroup\$ @ceilingcat Ty! \$\endgroup\$ Commented Mar 1, 2023 at 1:12
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Thunno 2, 3 bytes

ƘƇ~

Try it online!

Explanation

ƘƇ~  # Implicit input
Ƙ    # First integer where:
 Ƈ~  #  Not in input
     # Implicit output
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.