# Minimum excluded number

This is intended to be an easy, bite-size code-golf.

The mex (minimal excluded number) of a finite collection of numbers is the smallest non-negative integer 0, 1, 2, 3, 4, ... that does not appear in the collection. In other words, it's the minimum of the complement. The mex operation is central to the analysis of impartial games in combinatorial game theory.

Your goal is to write a program or named function to compute the mex using as few bytes as possible.

Input:

A list of non-negative integers in any order. May contain repeats. For concreteness, the length of the list and the allowed range of elements will both be between 0 and 20 inclusive.

The definition of "list" here is flexible. Any structure that represents a collection of numbers is fine, as long as it has a fixed ordering of elements and allows repeats. It may not include any auxiliary information except its length.

The input can be taken as a function argument or through STDIN.

Output

The smallest excluded number. Output or print it.

Test cases

[1]
0
[0]
1
[2, 0]
1
[3, 1, 0, 1, 3, 3]
2
[]
0
[1, 2, 3]
0
[5, 4, 1, 5, 4, 8, 2, 1, 5, 4, 0, 7, 7]
3
[3, 2, 1, 0]
4
[0, 0, 1, 1, 2, 2, 3]
4
[1, 0, 7, 6, 3, 11, 15, 1, 9, 2, 3, 1, 5, 2, 3, 4, 6, 8, 1, 18]
10

• Restricting the numbers to a fixed range makes this problem even simpler. Sep 29, 2014 at 21:25
• @MartinBüttner If the array contains all number 0 to 20, the correct output is 21. I'll add a test case. Yes, the fixed range definitely makes it easier, though one could still arguably use sys.maxint or 2**64 if I didn't specify it.
– xnor
Sep 29, 2014 at 21:27
• No need for that test case. You said, the input can only contain 21 elements. Sep 29, 2014 at 21:28
• @MartinBüttner - I read ".. the length of the list and the allowed range of elements will both be between 0 and 20 inclusive" to mean that the list will have at most 20 elements. So, the highest output would be 20, given a list of all numbers starting with 0 and ending with 19. Am I wrong? Oct 1, 2014 at 0:10
• @KevinFegan Yes, the maximum possible output is 20. My comment was mistaken and I think MartinBüttner typoed.
– xnor
Oct 1, 2014 at 0:13

# Python, 37 characters

f=lambda a:min(set(range(21))-set(a))

• Beat me by a couple of seconds. BTW, it's range(21).
– qwr
Sep 29, 2014 at 22:04
• This seems to be the shortest solution. The recursive solution f=lambda l,i=0:i in l and f(l,i+1)or i is one char longer and the iterative solution i=0;l=input()\nwhile i in l:i+=1\nprint i is two chars longer (not storing the input makes it be taken repeatedly). Without the 20 bound, I think these approaches would prevail.
– xnor
Sep 30, 2014 at 20:33
• Couldn't this be an anonymous function? If it could, you can save 2 bytes. May 1, 2017 at 16:10

C# - 64 chars

int f(int[] a){return Enumerable.Range(0,20).Except(a).First();}


Not always Rarely the best golfing language, but is easy to write and understand :)

# Scala, 18 bytes

0 to 20 diff l min


l is a list of Int.

scala> val l = List(0,1,5)
l: List[Int] = List(0, 1, 5)

scala> 0 to 20 diff l min
res0: Int = 2


# PHP, 38 Bytes

<?=min(array_diff(range(0,20),$_GET));  ## PHP, 39 Bytes <?for(;in_array($i++,$_GET););echo$i-1;


# Java, 91 bytes

int f(int[]a){int i=0,j=1,k;for(;j>0;i++)for(k=j=0;k<a.length;j=a[k++]==i?1:j);return i-1;}


Try it online!

# Java 7, 69 66 bytes

int c(java.util.List a){int r=0;for(;a.contains(r);r++);return r;}


-3 bytes thanks to @LeakyNun

Explanation:

Supports not only 0-20, but 0-2147483647 instead (which actually saves bytes).

int c(java.util.List a){    // Method with List parameter and integer return-type
int r=0;                  //  Return integer
for(;a.contains(r);r++);  //  Continue raising r as long as the list contains the current r
return r;                 //  Return result-integer
}                           // End of method


Test code:

Try it here.

import java.util.ArrayList;
import java.util.Arrays;
class M{
static int c(java.util.List a){int r=0;for(;a.contains(r);r++);return r;}

public static void main(String[] a){
System.out.println(c(Arrays.asList(1)));
System.out.println(c(Arrays.asList(0)));
System.out.println(c(Arrays.asList(2, 0)));
System.out.println(c(Arrays.asList(3, 1, 0, 1, 3, 3)));
System.out.println(c(new ArrayList()));
System.out.println(c(Arrays.asList(1, 2, 3)));
System.out.println(c(Arrays.asList(5, 4, 1, 5, 4, 8, 2, 1, 5, 4, 0, 7, 7)));
System.out.println(c(Arrays.asList(3, 2, 1, 0)));
System.out.println(c(Arrays.asList(0, 0, 1, 1, 2, 2, 3)));
System.out.println(c(Arrays.asList(1, 0, 7, 6, 3, 11, 15, 1, 9, 2, 3, 1, 5, 2, 3, 4, 6, 8, 1, 18)));
}
}


Output:

0
1
1
2
0
0
3
4
4
10

• May 1, 2017 at 16:12
• 3 bytes off May 1, 2017 at 16:14

# APL (Dyalog), 19 bytes

(0⍳⍨⊢=⍳∘⍴)∘(⊂∘⍋⌷⊢)∪


Try it online!

I am probably missing out something important here. Golfing in progress...

# TI-BASIC, 24 bytes

:0→A                 //Store 0 to A
:Prompt X            //Prompt list X
:While not(prod(ʟX-A //While A is not missing from list X
:A+1→A               //Increment A
:End                 //End While loop
:A                   //Print A


If Prompt X is given a list instead of a single number, it will automatically create a list named X that can be accessed with ʟX.

• 20 bytes using Ans: Prompt X:0:While not(prod(ʟX-Ans:Ans+1:End:Ans Sep 24, 2018 at 9:01

# Japt, 7 bytes

@!UøXÃa
@    Ãa # Starting from zero, find the smallest integer
!UøX   # that's not present in the input array.


Try it online!

# Stax, 6 bytes

¢╔⌂♀╠▬


Run and debug it

Explanation

21r:IUI             # Full program, unpacked
21                  # Push 21
r                 # Range from 0...20
:I               # Find all elements in input that exist in range
U               # push -1
I              # Get index of first occurrence of


## F#, 38 bytes

let f s={0..20}|>Seq.except s|>Seq.min


Try it online!

Fairly straight-forward to be honest...

# Lua, 92 bytes

x=function(a,...)q=...or 0 for i=0,#a do if a[i]==q then return x(a,q+1)end end return q end


This seems way too long.

Try it online!

• 88 bytes
– c--
Sep 19, 2022 at 17:23

# APL (Dyalog Classic), 11 bytes

f←⊃⊢~⍨0,⍳∘⍴


Try it online!

# Wolfram Language (Mathematica), 29 bytes

Min@Complement[0~Range~20,#]&


Try it online!

# Stax, 5 bytes

wiix#


Run and debug it

w      run until condition is satisfied
ii    push iteration index twice
x#  number of times iteration index appears in input (non-zero is truthy)


When the loop is finished, the final iteration index will be on top of the main stack, and implicitly printed.

# Python 2, 36 bytes

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


Try it online!

# k, 7 bytes

*(!22)^


Try it online!

 (!22)  /[0, 1, 2, ..., 21]
^ /set difference between [0, 1, 2, ..., 21] and input (called exclude)
*       /get first element


For an arbitrary positive maximum instead of 20, the smallest I have so far is 13 bytes:

{*(!2+|/x)^x}


# Factor, 27 bytes

[ 21 iota swap diff first ]


Try it online!

       ! { 3 1 0 1 3 3 }
21     ! { 3 1 0 1 3 3 } 21
iota   ! { 3 1 0 1 3 3 } { 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 }
swap   ! { 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 } { 3 1 0 1 3 3 }
diff   ! { 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 }
first  ! 2


# Desmos, 52 bytes

L=[0...20]
f(l)=L[[(i-join(e,l))^2.minfori=L]>0].min


Try It On Desmos!

Try It On Desmos! - Prettified

# Zsh, 31 bytes

for ((;$@[(I)$[i]];i++)):
bye i


Attempt This Online! Outputs via exit code.

# 05AB1E, 6 5 bytes

₂ÝIKн


-1 byte thanks to @emanresuA

Explanation:

₂Ý     # Push a list in the range [0,26]
# (26 is the smallest 1-byte constant above 19)
IK   # Remove all values of the input-list from this ranged list
н  # Pop and push the first integer remaining (which is the minimum)
# (which is output implicitly as result)

• Would using a builtin number larger than 20 save bytes? Sep 19, 2022 at 9:06
• @emanresuA It indeed would, thanks. Sep 19, 2022 at 9:54

# Japt, 5 bytes

@øX}f


Try it here

@øX}f     :Implicit input of array U
@         :Function taking an integer X as an argument
øX       :  Does U contain X?
}      :End function
f     :First integer >=0 that returns false when passed through that function


## Japt -g, 5 bytes

Lo kU


Try it

Lo kU     :Implicit input of array U
L         :100
o        :Range [0,L)
kU     :Remove the elements of U
:Implicit output of first element


# Fig, $$\5\log_{256}(96)\approx\$$ 4.116 bytes

[FxmN


Try it online!

Works for all numbers.

[FxmN
mN # All natural numbers [0, 1, 2, 3, ...]
Fx   # Remove the inputs
[     # Take the first one remaining


# Pip, 7 bytes

WiNgUii


Takes input as separate command-line arguments. Try It Online!

### Explanation

WiNgUii
W        While
i       a number (initially 0)
N      is an element of
g     the list of command-line args:
Ui     Increment the number
i  Output the final value


f l=until(notEleml)(+1)0


Try it online!

# Haskell + hgl, 8 bytes

he<bD nn


Attempt This Online!

## Explanation

• bD nn all non-negative integers not in the input
• he get the first.

## Reflection

This is a very straight-forward solution to a very simple problem. The only thing I might say is that it could possibly be worth having a built-in for "The smallest natural number such that ...". Assuming that would be 3 bytes the built in would save 2 bytes in this case.

# x86_32 machine code, 14 13 bytes

-1 byte thanks to l4m2

Expects the array in EDI (as a uint8_t*) and the length in ECX as an integer. Returns output in EAX.

31 c0 9e 60 f2 ae 61 75 03 40 eb f7 c3


Try it online!

### Explanation

; eax=int calc_mex(edi=uint8_t* nums, ecx=int length)
calc_mex:
31 c0                   xor eax, eax ; N to look for (start at 0)

; Store 0 to EFLAGS so that when length is zero and scasb never runs,
; ZF is set to zero to return the proper result (0).
9e                      sahf

loop:
60                      pushad ; Store ECX and EDI

; Search for AL in *EDI. If it doesn't exist, return AL; if it does,
; increment AL and search again.
f2 ae                   repne scasb

61                      popad ; Restore ECX and EDI

; If AL was not found (ZF=0), return as we found the minimum.
75 03                   jnz return

; Otherwise, keep looping.
40                      inc eax
eb f7                   jmp loop

return:
c3                      ret

• Why check ecx rather than ZF?
– l4m2
Jan 7, 2023 at 13:40
• @l4m2 When inc ecx is removed and jecxz is converted to jnz, the empty list test case fails as scasb doesn't run and the jump is done based off of unrelated instructions (xor eax, eax on the first iteration and inc eax on the second). When inc ecx remains, test cases will fail randomly as al will occasionally be found in the extra checked byte. Jan 7, 2023 at 15:40
• -1
– l4m2
Jan 7, 2023 at 16:00

## Pascal, 148 bytes

This is a complete program meeting the specifications of ISO standard 7185 “Standard Pascal”. It expects a newline-separated possibly empty list of integers in the range 0..20.

program p(input,output);var i:0..20;s:set of 0..20;begin s:=[];while not EOF do begin readLn(i);s:=s+[i]end;i:=0;while i in s do i:=i+1;write(i)end.


Ungolfed:

program minimumExcludedNumber(input, output);
var
i: 0..20;
s: set of 0..20;
begin
{ transform ordered list to “unordered” set ―――――――――――――――――――――― }

{ Initialize s as an empty set. }
s := [];
{ This needs to be a head-controlled loop in order to
take account of a possibly _empty_ list of integers. }
while not EOF do
begin
s := s + [i]
end;

{ analyze step: find first integer not part of set ――――――――――――――― }

{ Starting at zero “skip” all _included_ numbers in s. }
i := 0;
while i in s do
begin
{ This is guaranteed not to cause an error [this concerns the case
that i equals 20], because as per specification “the length of
the list […] will […] be between 0 and 20 inclusive.” Specifying
all integers in the interval 0..20 would require _21_ items. }
i := i + 1
end;
write(i)
end.


# Nibbles, 2.5 bytes (5 nibbles)

/-,~


Attempt This Online!

/-,~    # full program
/-,~  # with implicit args
-   $# remove the input from ,~ # infinite list 0..infinity /$  # and fold from right over the resulting (infinite) list,
# returning the left-hand element each time


# *><>, 100 bytes

v           v       /&~1+I]:&1[D>20.
>l:?!\:1[D&0>:}}:{=?/&1-:&?!\{$}^ ;n /! {/  This one's a bit convoluted, so I don't plan on doing a full write-up. The gist, though, is to keep the initial input length (IIL) on a stack above our main one, keep the current index (CI) of the input that we're checking in the register, and to keep a counter value on the stack, leaving it at the 0th index when it comes time to print it. Checks for a value in the input by starting at the end of the input, and moving forward. Initialization - The part of Line 1 & 2 I don't mention later v >l:?!\:1[D&0  • Ensure the IP is on Line 2, and moving to the right • Get the length of the input • If it's 0, move down to Line 3 and print that • Otherwise, duplicate that IIL, and put one copy on a stack above our current one • And put another copy into the register Line 1 - Counter value is in input /&~1+I]:&1[D>20.  • Dump the register • Collapse the IIL down onto the current stack • Push a copy of the IIL into the register • Recreate the stack containing the IIL • Move the IP to [0, 2] in the code, placing it before the second v Line 2 - Test counter == input[CI], and handle not equal case >:}}:{=?/&1-:&?!\{$}^

• Ensure IP is moving to the right
• Duplicate the counter and input[CI]
• Move the stack such that a copy of the counter and a copy of the current index are next to each other
• If equal, move to Line 1
• Otherwise, reduce the CI by one
• Check if CI == 0, if so, move to Line 3
• Otherwise,
• Reduce CI by 1
• Move the last element of the input to input[1]
• Move up to Line 1, just before the jump to [0, 2], essentially creating a do ... while (...) loop

Line 3 - Print

;n   /!                    {/

• If we're printing from Line 2, shift the counter value to the end of the stack

Try it online!