# 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

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

# Perl 5-p, 28 bytes

$#i++;/\b$#i\b/&&redo;$_=$#i


Try it online!

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

# Powershell, 28 bytes

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


Test script:

$f = { for(;+$i-in$args){$i++}+$i #for(;$i++-in$args){}(--$i)   # alternative version
}

@(
,(0 , 1)
,(1 , 0)
,(2 , 3, 1, 0, 1, 3, 3)
,(0 )
,(0 , 1, 2, 3)
,(3 , 5, 4, 1, 5, 4, 8, 2, 1, 5, 4, 0, 7, 7)
,(4 , 3, 2, 1, 0)
,(4 , 0, 0, 1, 1, 2, 2, 3)
,(10, 1, 0, 7, 6, 3, 11, 15, 1, 9, 2, 3, 1, 5, 2, 3, 4, 6, 8, 1, 18)
) | % {
$e,$a = $_$r = &$f @a "$($r-eq$e): $r" }  Output: True: 0 True: 1 True: 2 True: 0 True: 0 True: 3 True: 4 True: 4 True: 10  Explanation: • Increment $i while the $args array contains the integer value +$i.
• Output a last integer value +$i. # 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  # Haskell, 26 bytes 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 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 at 15:40 • -1 – l4m2 Jan 7 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 readLn(i); 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.  See also natural supremum code golfing task and answer. # 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  ## Perl - 34 Here's a subroutine. sub f{$_~~@_?1:return$_ for0..20}  Test with: perl -e'print f(0,1,3,4,5,6,7); sub f{$_~~@_?1:return\$_ for 0..20}'