26
\$\begingroup\$

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
\$\endgroup\$
8
  • 2
    \$\begingroup\$ Restricting the numbers to a fixed range makes this problem even simpler. \$\endgroup\$ Commented Sep 29, 2014 at 21:25
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – xnor
    Commented Sep 29, 2014 at 21:27
  • 1
    \$\begingroup\$ No need for that test case. You said, the input can only contain 21 elements. \$\endgroup\$ Commented Sep 29, 2014 at 21:28
  • 1
    \$\begingroup\$ @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? \$\endgroup\$ Commented Oct 1, 2014 at 0:10
  • 2
    \$\begingroup\$ @KevinFegan Yes, the maximum possible output is 20. My comment was mistaken and I think MartinBüttner typoed. \$\endgroup\$
    – xnor
    Commented Oct 1, 2014 at 0:13

73 Answers 73

1
\$\begingroup\$

Python, 37 characters

f=lambda a:min(set(range(21))-set(a))
\$\endgroup\$
3
  • \$\begingroup\$ Beat me by a couple of seconds. BTW, it's range(21). \$\endgroup\$
    – qwr
    Commented Sep 29, 2014 at 22:04
  • \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Commented Sep 30, 2014 at 20:33
  • \$\begingroup\$ Couldn't this be an anonymous function? If it could, you can save 2 bytes. \$\endgroup\$
    – univalence
    Commented May 1, 2017 at 16:10
1
\$\begingroup\$

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

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

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

PHP, 38 Bytes

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

PHP, 39 Bytes

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

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!

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

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

APL (Dyalog), 19 bytes

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

Try it online!

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

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

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.

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

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!

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

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

F#, 38 bytes

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

Try it online!

Fairly straight-forward to be honest...

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

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!

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

APL (Dyalog Classic), 11 bytes

f←⊃⊢~⍨0,⍳∘⍴

Try it online!

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

Wolfram Language (Mathematica), 29 bytes

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

Try it online!

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

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.

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

Python 2, 36 bytes

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

Try it online!

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

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

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

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

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

Zsh, 31 bytes

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

Attempt This Online! Outputs via exit code.

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

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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Would using a builtin number larger than 20 save bytes? \$\endgroup\$
    – emanresu A
    Commented Sep 19, 2022 at 9:06
  • \$\begingroup\$ @emanresuA It indeed would, thanks. \$\endgroup\$ Commented Sep 19, 2022 at 9:54
1
\$\begingroup\$

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

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

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

Haskell, 26 bytes

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

Try it online!

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

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.

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

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
\$\endgroup\$
3
  • \$\begingroup\$ Why check ecx rather than ZF? \$\endgroup\$
    – l4m2
    Commented Jan 7, 2023 at 13:40
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Jan 7, 2023 at 15:40
  • \$\begingroup\$ -1 \$\endgroup\$
    – l4m2
    Commented Jan 7, 2023 at 16:00
1
\$\begingroup\$

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.

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

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

*><>, 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!

\$\endgroup\$

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.