Minimum excluded number

Question

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. — Martin Ender, 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. — Martin Ender, 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? — Kevin Fegan, 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

2xsaiko · Accepted Answer · 2017-04-30 20:47:44Z

1

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

answered Apr 30, 2017 at 20:47

2xsaiko

7494 silver badges7 bronze badges

Add a comment |

Jörg Hülsermann · Accepted Answer · 2017-04-30 21:10:57Z

1

PHP, 38 Bytes

<?=min(array_diff(range(0,20),$_GET));

PHP, 39 Bytes

<?for(;in_array($i++,$_GET););echo$i-1;

answered Apr 30, 2017 at 21:10

Jörg Hülsermann

13.3k3 gold badges14 silver badges36 bronze badges

Add a comment |

Leaky Nun · Accepted Answer · 2017-05-01 15:59:25Z

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!

answered May 1, 2017 at 15:59

Leaky Nun

49.6k6 gold badges107 silver badges281 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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:

\$\begingroup\$ Heh, libraries. \$\endgroup\$
– Leaky Nun
May 1, 2017 at 16:12 — Leaky Nun, May 1, 2017 at 16:12
\$\begingroup\$ 3 bytes off \$\endgroup\$
– Leaky Nun
May 1, 2017 at 16:14 — Leaky Nun, May 1, 2017 at 16:14

user41805 · Accepted Answer · 2017-05-01 17:32:04Z

1

APL (Dyalog), 19 bytes

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

Try it online!

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

answered May 1, 2017 at 17:32

user41805

13.1k6 gold badges40 silver badges87 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered May 2, 2017 at 0:04

Scott Milner

1,86610 silver badges22 bronze badges

\$\begingroup\$ 20 bytes using Ans: Prompt X:0:While not(prod(ʟX-Ans:Ans+1:End:Ans \$\endgroup\$
– JosiahRyanW
Sep 24, 2018 at 9:01

Add a comment |

Etheryte · Accepted Answer · 2018-05-07 17:16:31Z

1

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!

answered May 7, 2018 at 17:16

Etheryte

3,7982 gold badges19 silver badges24 bronze badges

Add a comment |

Multi · Accepted Answer · 2018-05-07 17:49:59Z

1

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

edited May 7, 2018 at 17:49

answered May 7, 2018 at 17:44

Multi

4752 silver badges7 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

F#, 38 bytes

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

Try it online!

Fairly straight-forward to be honest...

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered May 7, 2018 at 18:05

Ciaran_McCarthy

7791 gold badge4 silver badges9 bronze badges

Add a comment |

Xcali · Accepted Answer · 2018-05-07 18:21:59Z

1

Perl 5 `-p`, 28 bytes

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

Try it online!

answered May 7, 2018 at 18:21

Xcali

13.4k2 gold badges14 silver badges37 bronze badges

Add a comment |

ivzem · Accepted Answer · 2018-05-07 20:34:23Z

1

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!

answered May 7, 2018 at 20:34

ivzem

1,30911 silver badges16 bronze badges

\$\begingroup\$ 88 bytes \$\endgroup\$
– c--
Sep 19, 2022 at 17:23

Add a comment |

TwiNight · Accepted Answer · 2018-05-08 05:38:15Z

1

APL (Dyalog Classic), 11 bytes

f←⊃⊢~⍨0,⍳∘⍴

Try it online!

answered May 8, 2018 at 5:38

TwiNight

4,54016 silver badges26 bronze badges

Add a comment |

nixpower · Accepted Answer · 2018-10-09 22:43:19Z

1

Wolfram Language (Mathematica), 29 bytes

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

Try it online!

answered Oct 9, 2018 at 22:43

nixpower

1813 bronze badges

Add a comment |

recursive · Accepted Answer · 2018-10-09 23:57:14Z

1

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.

answered Oct 9, 2018 at 23:57

recursive

10.4k19 silver badges36 bronze badges

Add a comment |

Chas Brown · Accepted Answer · 2018-10-10 07:00:03Z

1

Python 2, 36 bytes

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

Try it online!

edited Oct 10, 2018 at 7:00

answered Oct 10, 2018 at 6:50

Chas Brown

9,7471 gold badge12 silver badges39 bronze badges

Add a comment |

mazzy · Accepted Answer · 2018-10-10 07:53:07Z

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.

zgrep · Accepted Answer · 2018-10-11 03:01:16Z

1

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}

answered Oct 11, 2018 at 3:01

zgrep

1,5817 silver badges9 bronze badges

Add a comment |

chunes · Accepted Answer · 2022-09-04 09:21:48Z

1

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

answered Sep 4, 2022 at 9:21

chunes

22.7k3 gold badges21 silver badges51 bronze badges

Add a comment |

Aiden Chow · Accepted Answer · 2022-09-04 15:40:43Z

1

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

answered Sep 4, 2022 at 15:40

Aiden Chow

12.6k1 gold badge14 silver badges53 bronze badges

Add a comment |

pxeger · Accepted Answer · 2022-09-19 08:16:15Z

1

Zsh, 31 bytes

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

Attempt This Online! Outputs via exit code.

edited Sep 19, 2022 at 8:16

answered Sep 19, 2022 at 8:04

pxeger

23.3k4 gold badges52 silver badges135 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-09-19 09:54:34Z

1

05AB1E, 6 5 bytes

₂ÝIKн

-1 byte thanks to @emanresuA

Try it online or verify all test cases.

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)

edited Sep 19, 2022 at 9:54

answered Sep 19, 2022 at 8:31

Kevin Cruijssen

123k11 gold badges135 silver badges374 bronze badges

1

\$\begingroup\$ Would using a builtin number larger than 20 save bytes? \$\endgroup\$
– emanresu A
Sep 19, 2022 at 9:06
\$\begingroup\$ @emanresuA It indeed would, thanks. \$\endgroup\$
– Kevin Cruijssen
Sep 19, 2022 at 9:54

Add a comment |

Shaggy · Accepted Answer · 2022-09-19 15:57:49Z

1

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

edited Sep 19, 2022 at 15:57

answered Sep 19, 2022 at 8:33

Shaggy

41.5k4 gold badges34 silver badges92 bronze badges

Add a comment |

Seggan · Accepted Answer · 2022-09-23 21:14:10Z

1

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

answered Sep 23, 2022 at 21:14

Seggan

5,27121 silver badges47 bronze badges

Add a comment |

DLosc · Accepted Answer · 2022-09-24 00:57:42Z

1

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

answered Sep 24, 2022 at 0:57

DLosc

38k5 gold badges67 silver badges131 bronze badges

Add a comment |

xnor · Accepted Answer · 2022-09-24 08:44:40Z

1

Haskell, 26 bytes

f l=until(`notElem`l)(+1)0

Try it online!

answered Sep 24, 2022 at 8:44

xnor

144k26 gold badges273 silver badges637 bronze badges

Add a comment |

Wheat Wizard · Accepted Answer · 2023-01-04 03:35:28Z

1

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.

answered Jan 4 at 3:35

Wheat Wizard♦

96.5k19 gold badges276 silver badges638 bronze badges

Add a comment |

engineer gaming · Accepted Answer · 2023-01-07 19:15:43Z

x86_32 machine code, ¹⁴ 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

@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. — engineer gaming, Jan 7 at 15:40

Kai Burghardt · Accepted Answer · 2023-03-04 14:32:16Z

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.

Dominic van Essen · Accepted Answer · 2023-09-12 11:28:27Z

1

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

answered Sep 12 at 11:28

Dominic van Essen

34.6k2 gold badges18 silver badges54 bronze badges

Add a comment |

hmatt1 · Accepted Answer · 2014-09-29 21:53:56Z

0

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

answered Sep 29, 2014 at 21:53

hmatt1

3,4561 gold badge17 silver badges36 bronze badges

Add a comment |

Minimum excluded number

71 Answers 71

Scala, 18 bytes

PHP, 38 Bytes

PHP, 39 Bytes

Java, 91 bytes

Java 7, 69 66 bytes

APL (Dyalog), 19 bytes

TI-BASIC, 24 bytes

Japt, 7 bytes

Stax, 6 bytes

F#, 38 bytes

Perl 5 -p, 28 bytes

Lua, 92 bytes

APL (Dyalog Classic), 11 bytes

Wolfram Language (Mathematica), 29 bytes

Stax, 5 bytes

Python 2, 36 bytes

Powershell, 28 bytes

k, 7 bytes

Factor, 27 bytes

Desmos, 52 bytes

Zsh, 31 bytes

05AB1E, 6 5 bytes

Japt, 5 bytes

Japt -g, 5 bytes

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

Pip, 7 bytes

Explanation

Haskell, 26 bytes

Haskell + hgl, 8 bytes

Explanation

Reflection

x86_32 machine code, 14 13 bytes

Explanation

Pascal, 148 bytes

Nibbles, 2.5 bytes (5 nibbles)

Perl - 34

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Perl 5 `-p`, 28 bytes

Japt `-g`, 5 bytes

x86_32 machine code, ¹⁴ 13 bytes

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