# 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 '14 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 '14 at 21:27
• No need for that test case. You said, the input can only contain 21 elements. Sep 29 '14 at 21:28
• @MartinBüttner Right, fencepost. Thanks.
– xnor
Sep 29 '14 at 21:29
• @KevinFegan Yes, the maximum possible output is 20. My comment was mistaken and I think MartinBüttner typoed.
– xnor
Oct 1 '14 at 0:13

# Pyth, 6 bytes

h-U21Q


# Example run

$pyth -c h-U21Q <<< '[5, 4, 1, 5, 4, 8, 2, 1, 5, 4, 0, 7, 7]' 3  ### How it works  U21 range(21) Q eval(input()) -U21Q setwisedifference(range(21), eval(input)) # Pyth function. Preserves order. h-U21Q setwisedifference(range(21), eval(input))[0]  • When the set is converted to list, is it always in sorted order? – xnor Sep 30 '14 at 3:40 • Pyth's set difference preserves the order of the first argument (range(21)), which is ordered. (This also means the explanation isn't entirely accurate. Pyth and Python 3 are both fairly new to me.) Sep 30 '14 at 3:48 • To clarify, - in Pyth is actually a filter - it filters the first argument for absence from the second argument, then converts it to the form of the first argument (string, list or set). Oct 1 '14 at 6:55 • Also, Dennis, it should be h-U22Q so it will give the correct output of 21 on the input containing the full allowable range. Oct 1 '14 at 6:57 • @isaacg: The list's length is also limited to 20, so it cannot contain all 21 numbers from 0 to 20. Oct 1 '14 at 13:06 ## CJam, 11 8 bytes K),l~^1<  How it works: K), "Create an array with numbers 0 through 20" l~ "Read the input and eval it, resulting to an array" ^ "XOR the elements of two arrays, resulting in a complement array" 1< "Take the first element of the resultant array"  Sample input: [1 0 7 6 3 11 15 1 9 2 3 1 5 2 3 4 6 8 1 18]  Output: 10  Try it online here • How high do the single-character numbers in CJam go? – xnor Sep 29 '14 at 21:47 • @xnor Sadly, 20 - sourceforge.net/p/cjam/wiki/Variables Sep 29 '14 at 21:48 • A lucky choice! – xnor Sep 29 '14 at 21:50 # J - 13 char f=:0{i.@21&-.  Very simple actions in J, and thus very hard to make smaller. i.@21 creates a list from 0 to 20 inclusive. -. performs set-subtracts the input from this list. 0{ takes the first element of what's left, i.e. the smallest number. f=: defines a named function. At the REPL:  f=:0{(i.21)&-. f 1 0 f 0 1 f 2 0 1 f 3 1 0 1 3 3 2 f '' NB. empty list 0 f 1 2 3 0 f 5 4 1 5 4 8 2 1 5 4 0 7 7 3 f 3 2 1 0 4 f 0 0 1 1 2 2 3 4 f 1 0 7 6 3 11 15 1 9 2 3 1 5 2 3 4 6 8 1 18 10  Since the release of J806 in November 2017, a new syntax exists which saves us one byte by letting us use i.@21 for the old (i.21) in this context. • Do you need f=:? May 2 '17 at 0:44 • Since November 2017 i.@21-.] would save 1 byte. May 7 '18 at 16:26 # Golfscript 7 ~21,^0=  A further-golfed version of Peter Taylor's answer. Community wiki since I don't have the rep to comment on his post. The difference is using the known max list size from the question instead of length +1 to save a character and dropping the irrelevant$.

Try it online

• Dammit Golfscript for saving 1 character so as to not read the input -_- Sep 29 '14 at 22:01

# Burlesque - 9 Bytes

20rzj\\<]


Takes input from stdin in the format {7 6 5 5 1 2 2 4 2 0}

Explained:

 20 rz   map a range from 0 to 20. (thanks to algorithmshark for the cocde fix)
j \\    swaps the two arrays, and collects the difference between the two into a new array
<]      gets the smallest element of the resulting array.


Try some examples:

{1 0 7 6 3 11 15 1 9 2 3 1 5 2 3 4 6 8 1 18}20rzj\\<]

{5 4 1 5 4 8 2 1 5 4 0 7 7}20rzj\\<]

• This fails to give any output on the input {0 1 2}, because you need to rz one more than the largest number. Just going straight for 20rzj\\<] fixes this and saves a char. Sep 30 '14 at 17:09
• @algorithmshark No way around it, you are very right. Fixed. And thank you. Sep 30 '14 at 17:34

## Ruby, 32 bytes

f=->n{(0..20).find{|i|n-[i]==n}}


Defines a function f to be called with an array.

• Any comments from the downvoter? Did I miss some part of the spec? Sep 30 '14 at 13:19
• I doubt it. Several other answers (including mine) got a mystery downvote. Sep 30 '14 at 15:25
• @ipi but it does... in exactly the same format given in the examples in the challenge posts, e.g. f[[0, 1]] (where the outer brackets are invocation syntax and the inner brackets define the array). Sep 30 '14 at 16:07
• Why do you need the f=? May 2 '17 at 0:47

# Bash+coreutils, 23 bytes

seq 0 20|egrep -vwm1 $1  This assumes input as a | (pipe) separated list. E.g: $ ./mex.sh "5|4|1|5|4|8|2|1|5|4|0|7|7"
3
$ • I don't think you need "(...)" around the $1. Sep 30 '14 at 16:42
• Pipe-separated is fine, it meets the list-like condition of the spec.
– xnor
Sep 30 '14 at 20:35

~.,),^$0=  Takes input from stdin in the format [5 4 1 5 4 8 2 1 5 4 0 7 7]. Online demo • Shouldn't the ; before the input string be counted in the program itself ? Sep 29 '14 at 22:20 • @Optimizer, that's simulating input from stdin because the online GolfScript site doesn't support a separate input field. Sep 29 '14 at 22:52 # Xojo, 55 bytes dim x as int8 while a.indexOf(x)>-1 x=x+1 wend return x  # Ruby, 22 x=->n{([*0..20]-n)[0]}  ## Explanation • Input is taken as an argument to a lambda. It expects an Array of Integers. • The input is subtracted from the array [0,1,2..20]. • Because the Array [0,1,2..20] is sorted, the first element must be the mex. • Sweet, that was my first attempt, but I couldn't get the destructuring to work - I didn't think of surrounding it with brackets. Btw, you can use 20 instead of 21, because the input can only contain 20 elements. Sep 29 '14 at 22:38 # Haskell, 30 f s=filter(notElems)[0..]!!0  This works for lists of all size and lists beyond 20. This can be made 15 bytes long if Data.List is imported: f s=[0..]\\s!!0  ## Scheme - 219 (define (A X) (define (B X) (if (equal? (length X) 1) (+ (car X) 1) (if (< (- (cadr X) (car X)) 2) (B (cdr X)) (+ (car X) 1)))) (if (empty? X) () (if (equal? (car (sort X <)) 0) (B (sort X <)) (- (car (sort X <)) 1))))  Not very competitive. But I like writing scheme :), Here's the ungolfed code: (define (minExclude X) (define (firstNonOneDifference X) (if (equal? (length X) 1) (+ (car X) 1) (if (< (- (cadr X) (car X)) 2) (firstNonOneDifference (cdr X)) (+ (car X) 1) )) ) (let ([s (sort X <)]) (if (empty? X) () (if (equal? (car s) 0) (firstNonOneDifference s) (- (car s) 1) )) ) )  # 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 '14 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 '14 at 20:33 • Couldn't this be an anonymous function? If it could, you can save 2 bytes. May 1 '17 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  # 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 '17 at 16:12 • 3 bytes off May 1 '17 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 '18 at 9:01 # 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  # APL (Dyalog Classic), 11 bytes f←⊃⊢~⍨0,⍳∘⍴  Try it online! # Jelly, 7 bytes Another approach. Can be used in a chain with any arity, and doesn't need chain separator or anything. ‘Ṭ;0i0’  Because the answer is guaranteed to be less than 256, this also works: # Jelly, 5 bytes ⁹ḶḟµḢ  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.

# MathGolf, 5 4 bytes

Jr,╓


Try it online!

This solution is restricted to just the range 0 to 20, though this can be extended easily by increasing the initial range.

### Explanation:

Jr     Range from 0 to 20
,    Remove elements from the input list from this range
╓   Return the minimum element


Alternatively, a 5 byte solution for all numbers:

Åï╧▲ï


Try it online!

### Explanation:

Å  ▲   Do while true
╧    Does the input contain
ï     The index of the loop?
ï  Push the number of iterations of the last loop

• With the new changes that are (hopefully) being added to TIO today, there's a 4 byte solution to this problem. It is restricted to an upper limit defined in the code, but since MathGolf has a 1-byte literal for 10^8, it shouldn't be noticeable.
– maxb
Nov 27 '18 at 11:16
• This was the exact solution I had (I used Z instead of J because I was lazy).
– maxb
Nov 28 '18 at 7:41

## 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}'


## Java, 93

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


Ungolfed:

int f(int[] a) {
int i = 0, j = 0, length = a.length;
for (; i < 20 & j < length; i++) {
for (j = 0; j < length && a[j] != i; j++) { }
}
return i - 1;
}

• Produces -1 for test case []. Sep 30 '14 at 16:08

# Cobra - 50

def f(l)
for n in 22,if n not in l,break
print n


## Javascript, 74

i=-1;a=prompt().split(',');while(i<21&&a.indexOf(String(++i))>=0);alert(i)


Nice and simple! Note the empty while loop.

# JavaScript (E6) 35

Recursive function, array parameter in input and returning the mex. Not limited to 20

F=(l,i=0)=>~l.indexOf(i)?F(l,++i):i


Test in FireFox/FireBug console

;[[1],[0],[2, 0],[3, 1, 0, 1, 3, 3],[],[1, 2, 3],
[5, 4, 1, 5, 4, 8, 2, 1, 5, 4, 0, 7, 7],[3, 2, 1, 0],[0, 0, 1, 1, 2, 2, 3],
[1, 0, 7, 6, 3, 11, 15, 1, 9, 2, 3, 1, 5, 2, 3, 4, 6, 8, 1, 18]]
.forEach(list => console.log(list, F(list)))


Output

[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


# PHP, 38 Bytes

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