title: Shift right by half a bit

text:
# Question
Title: Shift right by half a bit
The challenge is to implement a program or function <sup>(subsequently referred to as "program")</sup> that takes a nonnegative integer \\$n\\$ as input and returns \\$n\over\sqrt{2}\\$ (the input divided by the square root of two) as output, rounded to a nonnegative integer.

You may take your input and output in any reasonable format; for example stdin/stdout, files, or arguments/return values would all be acceptable.

You are required to use, at minimum, the largest fixed-size integer type offered by your language, and if an **unsigned** variant of this is available, you must use it. If your language has no built-in integer type (e.g. JavaScript) you are allowed to use its default numerical type (e.g. floating point); for languages with no concept of a number (e.g. regex), input and output can be e.g. the length of a string.

It is not required to reject negative integers; a submission that returns correct answers for negative inputs is allowed, but not required. Undefined behavior with negative inputs is allowed.

You are allowed and encouraged to use arbitrary-precision integer types if you so desire, but the type must either be a built-in, part of a standard library, or implemented from scratch in your program. As such, there are two categories of competition in this challenge:

1. Precision limited by built-in types (fixed-size integer, floating point, etc.)
2. Arbitrary precision (recursion and memory allocation, if used, can be assumed to be unlimited, where appropriate to the language in question)

Despite what the title might imply, you may use any rounding algorithm you want (floor, ceiling, nearest half up, nearest half even, arbitrary, or even random), as long as the difference between the integer returned value and the theoretical exact (irrational) value is always less than \\$1\\$ for all inputs that fit in your chosen integer type (but exactly 0 for an input of 0). All inputs up to the maximum representable value must return a correct output.

In a way, the job of this program is to calculate the irrational number \\$\sqrt{2}\\$ to the requested precision, presenting it in the form of an integer. This is why solutions using arbitrary-precision types are encouraged, but not required.

This is a challenge. Standard loopholes are denied. The program with the least number of bytes wins. That said, this challenge is not only about which answer wins overall; it's also about seeing how concisely the challenge can be solved in each language, seeing how each language "prefers" to handle rounding, and how hard it is to solve in esoteric languages. And for those submissions that choose to use arbitrary precision, it's about seeing how concisely this can be done in the language.

# Test cases

Within the Precision-limited category, only the cases that are in range of the language's capability are required to pass.

If your solution is too slow to demonstrably pass the larger inputs (or runs out of memory/stack), it becomes all the more important to explain it sufficiently well, so that it can be understood that it would pass.

```
Input → Floor or Ceiling
0 → 0 (this is the only input that can only result in one valid output)
1 → 0 or 1
2 → 1 or 2
3 → 2 or 3
4 → 2 or 3
5 → 3 or 4
10 → 7 or 8
32 → 22 or 23
500 → 353 or 354
1000 → 707 or 708
1000000 → 707106 or 707107
186444716 → 131836322 or 131836323
1000000000 → 707106781 or 707106782
2147483647 → 1518500249 or 1518500250
3037000499 → 2147483647 or 2147483648
4294967295 → 3037000499 or 3037000500
4503599627370496 → 3184525836262886 or 3184525836262887
9223372036854775807 → 6521908912666391105 or 6521908912666391106
18446744073709551615 → 13043817825332782211 or 13043817825332782212
10000000000000000000000000000000000000 → 7071067811865475244008443621048490392 or 7071067811865475244008443621048490393
956287480911872131784896176254337633353980911149964074434383 → 676197362516585909969655173274459790030028262421622111830069 or 676197362516585909969655173274459790030028262421622111830070

```

# Answer
# Regex (ECMAScript+`(?*)`), ~~1169~~ ~~929~~ ~~887~~ ~~853~~ ~~849~~ 708 bytes

*-141 bytes by using the second form of shortened division, where \\$A^2 \> C\\$*

Regex was never designed to do mathematics. It has no concept of arithmetic. However, when input is taken in the form of bijective unary, as a sequence of identical characters in which the length represents a natural number, it is possible to do a wide range of operations, building up from the simple primitives available, which basically amount to addition, comparison, multiplication by a constant, and modulo. Everything must fit inside the input; it isn't possible to directly operate on numbers larger than that.

In ECMAScript regex, it's especially difficult (and therefore interesting) to do even some of the simplest of operations, because of the limitation that all backrefs captured in a loop are reset to empty at the beginning of each iteration – which makes it impossible to count anything directly. It's nevertheless possible to match prime numbers, powers of N, Nth powers, arbitrary multiplication and exponentiation, Fibonacci numbers, factorial numbers, abundant numbers, and more, much of which is demonstrated in my other answers.

One of the operations that turns out to be far more verbose than the rest is to "calculate an irrational number". I initially discussed this with teukon back in 2014. The only known way to do this is to *emulate* operations on numbers larger than the input, and probably the simplest way to do this is by working in a number base chosen based on what can fit into the input.

It wasn't until late 2018 that I finally set about to implementing the theory I had sketched in 2014. Implementing it involved adapting the multiplication algorithm to work with factors of 0, which turned out to golf rather elegantly. (The underlying multiplication algorithm is explained in this post.) The basic algorithm is this:

For input \\$N\\$, we want to calculate \\$M=\lfloor{N\over\sqrt2}\rfloor\\$. So we want the largest \\$M\\$ such that \\$2M^2\le N^2\\$.

If we take the "number base" to be \\$k=\lceil\sqrt N\rceil\\$ or \\$\lfloor\sqrt N\rfloor\\!+\\!1\\$, all multiplication operations \\$m\cdot n\\$ on \\$0\leq m,n\<k\\$ are guaranteed to fit in the available space.

So if \\$N=A k+B\\$, where \\$0\leq A,B\lt k\\$, we can calculate \\$N^2\\$:

$$N^2=(A k+B)^2=A^2 k^2+2 A B k+B^2$$

We must then do division, modulo, and carry to bring \\$A^2\\$, \\$2 A B\\$, and \\$B^2\\$ back into the range of a base \\$k\\$ "digit". A similar operation is then done to calculate \\$2 M^2\\$ iterated over the decreasing consecutive possible values of \\$M\\$, using digit-by-digit comparison to test for \\$2M^2\le N^2\\$, until the first \\$M\\$ is found that passes the test.

So while the basic concept is simple enough, it adds up to a lot of calculations, and the regex is huge! And this is probably the *simplest* calculation of an irrational number that can be done in ECMAScript regex. (It is still unknown whether it's possible to calculate a transcendental number to arbitrary precision in regex.)

This regex uses **molecular lookahead**, a.k.a. non-atomic lookahead, represented as `(?*`...`)`. Without this feature, it would be much harder (or at least much more verbose) to implement.

A choice I made early on, to depart from pure code golf by going for mathematical aesthetics, turned out to be a very interesting. I chose to use \\$k=\lceil\sqrt N\rceil\\$ because it has the very neat property of making the calculations fit perfectly into \\$N\\$ if \\$N\\$ is a perfect square, whereas \\$k=\lfloor\sqrt N\rfloor\\!+\\!1\\$ is basically chaotic for all inputs. They both yield the same final outputs, but the former is just cleaner. A few golfs later, this choice ended up net increasing the total length of the regex by **8 bytes**, so I figured it was worth it. (This change is in the git version history.) But another golf later that day, unbeknownst to me, was actually dependent on that decision! The skipping of a divisibility check in a division calculation makes \\$N=25\\$ return the incorrect output of \\$M=11\\$ instead of \\$M=17\\$ if \\$k=\lfloor\sqrt N\rfloor\\!+\\!1\\$, but works perfectly for all inputs if \\$k=\lceil\sqrt N\rceil\\$. So the *actual* net change in byte length was zero! It was a purely aesthetic decision for over two years.

At the time I did not understand why that division optimization worked, but this is now fully explained thanks to H.PWiz. The shortened form of division ~~used at the beginning of the calculation of \\$M^2\\$~~ gives the correct quotient \\$B\\$ when \\$A+2 \< 4B\\$, where \\$C\\$ is the dividend and \\$A\\$ is the divisor. Previously I believed that it was only guaranteed to work when \\$A \le B\\$. \[This is no longer used, due to the number base switch.\]

And now, with the discovery of a second shortened form of division that gives the correct quotient when \\$A^2 \> C\\$, I found a *major* opportunity to use it in this regex! It *only* works when \\$k=\lfloor\sqrt N\rfloor\\!+\\!1\\$, so now I've switched back to that number base. It's saving *141 bytes!* It's oddly convenient that this just happened to exist and works perfectly for this exact use.

`(?=(x(x*)).*(?=\1*$)\2+$)(?=(x\1)+(x?(x*)))(?=\4(x(x*?))\1+$)(?=.*(?=(?=\4*$)\4\5+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\9))(?=.*(?=(?=\4*$)(?=\6*$)(?=\4\7+$)\6\5+$|$\4)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\13))(?=.*(?=\12\12\9$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\17))(?*.*?(?=((?=\3*(x?(x*)))\21(x(x*?))\1+$)))(?=.*(?=\23*$)(\23\24+$))(?=.*(?=(?=\21*$)\21\22+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\27))(?=.*(?=(?=\21*$)(?=\23*$)(?=\21\24+$)\23\22+$|$\21)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\31))(?=.*(?=\30\30\27$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\35))(?=.*(?=\26\26)(?=\3*(x*))(\1(x)|))(?=.*(?=\34\34\40)(?=\3*(x*))(\1(x)|))(?=(?=(.*)\13\13\17(?=\6*$)\6\7+$)\44(x+|(?=.*(?!\16)\41|(?!.*(?!\38)\8).*(?=\16$)\41$))(\25\31\31\35){2}\43$)\20|xx?\B|`

Try it on repl.it

This regex is on GitHub with a full version history.

```
# Given an input number N in the domain ^x*$, this regex returns floor(N / sqrt(2))
(?=
    (x(x*))                    # \1 = will be the square root of the main number, rounded down; \2 = \1 - 1
    .*(?=\1*$)
    \2+$
)

# Step 1: Calculate N*N in base floor(sqrt(N))+1. Thanks to this choice of number base to work in, we'll be able to use the
# second shortened form of division in all places where the number base is the divisor, because it's guaranteed to give the
# correct quotient when the dividend is less than the squared divisor, and N itself is less than this. This form of division
# can be recognized by its lazy rather than greedy matching of the quotient, and only one divisibility test following that.

(?=(x\1)+(x?(x*)))             # \3 = \1+1 = floor(sqrt(N))+1, the number base to work in; \4 = N % \3; \5 = \4-1, or 0 if \4==0
(?=
    \4
    (x(x*?))                   # \6 = floor(N / \3); \7 = \6-1
    \1+$
)
(?=
    .*
    (?=
        (?=\4*$)               # tail = \4 * \4
        \4\5+$
    )
    (x*?)(?=\3*$)              # \8 =       (\4 * \4) % \3, the base-\3 digit in place 0 of the result for N*N
    (x?(x*?))                   # \9 = floor((\4 * \4) / \3); \10 = \9-1, or 0 if \9==0
    (
        \1+$
    |
        $\9                    # must make a special case for \9==0, because \1 is nonzero
    )
)
(?=
    .*
    (?=
        (?=\4*$)               # tail = \4 * \6; must do symmetric multiplication, because \4 is occasionally 1 larger than \6
        (?=\6*$)
        (?=\4\7+$)
           \6\5+$
    |
        $\4                    # must make a special case for \4==0, because \6 might not be 0
    )
    (x*?)(?=\3*$)              # \12 =       (\4 * \6) % \3
    (x?(x*?))                  # \13 = floor((\4 * \6) / \3); \14 = \13-1, or 0 if \13==0
    (
        \1+$
    |
        $\13                   # must make a special case for \13==0, because \1 is nonzero
    )
)
(?=
    .*(?=\12\12\9$)            # tail =       2 * \12 + \9
    (x*?)(?=\3*$)              # \16 =       (2 * \12 + \9) % \3, the base-\3 digit in place 1 of the result for N*N
    (x?(x*?))                  # \17 = floor((2 * \12 + \9) / \3); \18 = \17-1, or 0 if \17==0
    (
        \1+$
    |
        $\17                   # must make a special case for \17==0, because \1 is nonzero
    )
)                              # {\6*\6 + 2*\13 + \17} = the base-\3 digit in place 2 of the result for N*N, which is allowed to exceed \3 and will always do so;
                               # Note that it will be equal to N iff N is a perfect square, because of the choice of number base.

# Step 2: Find the largest M such that 2*M*M is not greater than N*N

# Step 2a: Calculate M*M in base \3
(?*
    .*?                        # Determine value of M with backtracking, starting with largest values first
    (?=
        (                      # \20 =       M
            (?=\3*(x?(x*)))\21 # \21 =       M % \3; \22 = \21-1, or 0 if \21==0
            (x(x*?))           # \23 = floor(M / \3); \24 = \23-1
            \1+$
        )
    )
)
(?=
    .*
    (?=\23*$)
    (\23\24+$)                 # \25 = \23 * \23
)
(?=
    .*
    (?=
        (?=\21*$)              # tail = \21 * \21
        \21\22+$
    )
    (x*?)(?=\3*$)              # \26 =       (\21 * \21) % \3, the base-\3 digit in place 0 of the result for M*M
    (x?(x*?))                  # \27 = floor((\21 * \21) / \3); \28 = \27-1, or 0 if \27==0
    (
        \1+$
    |
        $\27                   # must make a special case for \27==0, because \1 is nonzero
    )
)
(?=
    .*
    (?=
        (?=\21*$)              # tail = \21 * \23; must do symmetric multiplication, because \21 is occasionally 1 larger than \23
        (?=\23*$)
        (?=\21\24+$)
           \23\22+$
    |
        $\21                   # must make a special case for \21==0, because \23 might not be 0
    )
    (x*?)(?=\3*$)              # \30 =       (\21 * \23) % \3
    (x?(x*?))                  # \31 = floor((\21 * \23) / \3); \32 = \31-1, or 0 if \31==0
    (
        \1+$
    |
        $\31                   # must make a special case for \31==0, because \1 is nonzero
    )
)
(?=
    .*(?=\30\30\27$)           # tail =       2 * \30 + \27
    (x*?)(?=\3*$)              # \34 =       (2 * \30 + \27) % \3, the base-\3 digit in place 1 of the result for M*M
    (x?(x*?))                  # \35 = floor((2 * \30 + \27) / \3); \36 = \35-1, or 0 if \35==0
    (
        \1+$
    |
        $\35                   # must make a special case for \35==0, because \1 is nonzero
    )
)                              # {\25 + 2*\31 + \35} = the base-\3 digit in place 2 of the result for M*M, which is allowed to exceed \3 and will always do so

# Step 2b: Calculate 2*M*M in base \3
(?=
    .*
    (?=\26\26)                 # tail =       2*\26
    (?=\3*(x*))                # \38 =       (2*\26) % \3, the base-\3 digit in place 0 of the result for 2*M*M
    (\1(x)|)                   # \40 = floor((2*\26) / \3) == +1 carry if {2*\26} does not fit in a base \3 digit
)
(?=
    .*
    (?=\34\34\40)              # tail =       2*\34 + \40
    (?=\3*(x*))                # \41 =       (2*\34 + \40) % \3, the base-\3 digit in place 1 of the result for 2*M*M
    (\1(x)|)                   # \43 = floor((2*\34 + \40) / \3) == +1 carry if {2*\34 + \40} does not fit in a base \3 digit
)                              # 2*(\25 + 2*\31 + \35) + \43 = the base-\3 digit in place 2 of the result for 2*M*M, which is allowed to exceed \3 and will always do so

# Step 2c: Require that 2*M*M <= N*N

(?=
    (?=
        (.*)                   # \44
        \13\13\17
        (?=\6*$)               # tail = \6 * \6
        \6\7+$
    )
    \44                        # tail = {\6*\6 + 2*\13 + \17}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
    (
        x+
    |
        (?=
            .*(?!\16)\41       # \41 < \16
        |
            (?!.*(?!\38)\8)    # \38 <= \8
            .*(?=\16$)\41$     # \41 == \16
        )
    )
    (\25\31\31\35){2}\43$      # 2*(\25 + 2*\31 + \35) + \43
)

\20

|xx?\B|                        # handle inputs in the domain ^x{0,4}$

```

---

# Regex (ECMAScript 2018), ~~861~~ 720 bytes

This is a direct port of the ~~849~~ 708 byte molecular lookahead version, using variable length lookbehind.

`(?=(x(x*)).*(?=\1*$)\2+$)(?=(x\1)+(x?(x*)))(?=\4(x(x*?))\1+$)(?=.*(?=(?=\4*$)\4\5+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\9))(?=.*(?=(?=\4*$)(?=\6*$)(?=\4\7+$)\6\5+$|$\4)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\13))(?=.*(?=\12\12\9$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\17))(?=.*?(?=((?=\3*(x?(x*)))\21(x(x*?))\1+$))(?<=(?=(?=.*(?=\23*$)(\23\24+$))(?=.*(?=(?=\21*$)\21\22+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\27))(?=.*(?=(?=\21*$)(?=\23*$)(?=\21\24+$)\23\22+$|$\21)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\31))(?=.*(?=\30\30\27$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\35))(?=.*(?=\26\26)(?=\3*(x*))(\1(x)|))(?=.*(?=\34\34\40)(?=\3*(x*))(\1(x)|))(?=(?=(.*)\13\13\17(?=\6*$)\6\7+$)\44(x+|(?=.*(?!\16)\41|(?!.*(?!\38)\8).*(?=\16$)\41$))(\25\31\31\35){2}\43$))^.*))\20|xx?\B|`

Try it online!

This regex is on GitHub.

```
# Given an input number N in the domain ^x*$, this regex returns floor(N / sqrt(2))
(?=
    (x(x*))                    # \1 = will be the square root of the main number, rounded down; \2 = \1 - 1
    .*(?=\1*$)
    \2+$
)

# Step 1: Calculate N*N in base floor(sqrt(N))+1. Thanks to this choice of number base to work in, we'll be able to use the
# second shortened form of division in all places where the number base is the divisor, because it's guaranteed to give the
# correct quotient when the dividend is less than the squared divisor, and N itself is less than this. This form of division
# can be recognized by its lazy rather than greedy matching of the quotient, and only one divisibility test following that.

(?=(x\1)+(x?(x*)))             # \3 = \1+1 = floor(sqrt(N))+1, the number base to work in; \4 = N % \3; \5 = \4-1, or 0 if \4==0
(?=
    \4
    (x(x*?))                   # \6 = floor(N / \3); \7 = \6-1
    \1+$
)
(?=
    .*
    (?=
        (?=\4*$)               # tail = \4 * \4
        \4\5+$
    )
    (x*?)(?=\3*$)              # \8 =       (\4 * \4) % \3, the base-\3 digit in place 0 of the result for N*N
    (x?(x*?))                  # \9 = floor((\4 * \4) / \3); \10 = \9-1, or 0 if \9==0
    (
        \1+$
    |
        $\9                    # must make a special case for \9==0, because \1 is nonzero
    )
)
(?=
    .*
    (?=
        (?=\4*$)               # tail = \4 * \6; must do symmetric multiplication, because \4 is occasionally 1 larger than \6
        (?=\6*$)
        (?=\4\7+$)
           \6\5+$
    |
        $\4                    # must make a special case for \4==0, because \6 might not be 0
    )
    (x*?)(?=\3*$)              # \12 =       (\4 * \6) % \3
    (x?(x*?))                  # \13 = floor((\4 * \6) / \3); \14 = \13-1, or 0 if \13==0
    (
        \1+$
    |
        $\13                   # must make a special case for \13==0, because \1 is nonzero
    )
)
(?=
    .*(?=\12\12\9$)            # tail =       2 * \12 + \9
    (x*?)(?=\3*$)              # \16 =       (2 * \12 + \9) % \3, the base-\3 digit in place 1 of the result for N*N
    (x?(x*?))                  # \17 = floor((2 * \12 + \9) / \3); \18 = \17-1, or 0 if \17==0
    (
        \1+$
    |
        $\17                   # must make a special case for \17==0, because \1 is nonzero
    )
)                              # {\6*\6 + 2*\13 + \17} = the base-\3 digit in place 2 of the result for N*N, which is allowed to exceed \3 and will always do so;
                               # Note that it will be equal to N iff N is a perfect square, because of the choice of number base.

# Step 2: Find the largest M such that 2*M*M is not greater than N*N

# Step 2a: Calculate M*M in base \3
(?=
    .*?                            # Determine value of M with backtracking, starting with largest values first
    (?=
        (                          # \20 =       M
            (?=\3*(x?(x*)))\21     # \21 =       M % \3; \22 = \21-1, or 0 if \21==0
            (x(x*?))               # \23 = floor(M / \3); \24 = \23-1
            \1+$
        )
    )
    (?<=
        (?=
            (?=
                .*
                (?=\23*$)
                (\23\24+$)                 # \25 = \23 * \23
            )
            (?=
                .*
                (?=
                    (?=\21*$)              # tail = \21 * \21
                    \21\22+$
                )
                (x*?)(?=\3*$)              # \26 =       (\21 * \21) % \3, the base-\3 digit in place 0 of the result for M*M
                (x?(x*?))                  # \27 = floor((\21 * \21) / \3); \28 = \27-1, or 0 if \27==0
                (
                    \1+$
                |
                    $\27                   # must make a special case for \27==0, because \1 is nonzero
                )
            )
            (?=
                .*
                (?=
                    (?=\21*$)              # tail = \21 * \23; must do symmetric multiplication, because \21 is occasionally 1 larger than \23
                    (?=\23*$)
                    (?=\21\24+$)
                       \23\22+$
                |
                    $\21                   # must make a special case for \21==0, because \23 might not be 0
                )
                (x*?)(?=\3*$)              # \30 =       (\21 * \23) % \3
                (x?(x*?))                  # \31 = floor((\21 * \23) / \3); \32 = \31-1, or 0 if \31==0
                (
                    \1+$
                |
                    $\31                   # must make a special case for \31==0, because \1 is nonzero
                )
            )
            (?=
                .*(?=\30\30\27$)           # tail =       2 * \30 + \27
                (x*?)(?=\3*$)              # \34 =       (2 * \30 + \27) % \3, the base-\3 digit in place 1 of the result for M*M
                (x?(x*?))                  # \35 = floor((2 * \30 + \27) / \3); \36 = \35-1, or 0 if \35==0
                (
                    \1+$
                |
                    $\35                   # must make a special case for \35==0, because \1 is nonzero
                )
            )                              # {\25 + 2*\31 + \35} = the base-\3 digit in place 2 of the result for M*M, which is allowed to exceed \3 and will always do so

            # Step 2b: Calculate 2*M*M in base \3
            (?=
                .*
                (?=\26\26)                 # tail =       2*\26
                (?=\3*(x*))                # \38 =       (2*\26) % \3, the base-\3 digit in place 0 of the result for 2*M*M
                (\1(x)|)                   # \40 = floor((2*\26) / \3) == +1 carry if {2*\26} does not fit in a base \3 digit
            )
            (?=
                .*
                (?=\34\34\40)              # tail =       2*\34 + \40
                (?=\3*(x*))                # \41 =       (2*\34 + \40) % \3, the base-\3 digit in place 1 of the result for 2*M*M
                (\1(x)|)                   # \43 = floor((2*\34 + \40) / \3) == +1 carry if {2*\34 + \40} does not fit in a base \3 digit
            )                              # 2*(\25 + 2*\31 + \35) + \43 = the base-\3 digit in place 2 of the result for 2*M*M, which is allowed to exceed \3 and will always do so

            # Step 2c: Require that 2*M*M <= N*N

            (?=
                (?=
                    (.*)                   # \44
                    \13\13\17
                    (?=\6*$)               # tail = \6 * \6
                    \6\7+$
                )
                \44                        # tail = {\6*\6 + 2*\13 + \17}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
                (
                    x+
                |
                    (?=
                        .*(?!\16)\41       # \41 < \16
                    |
                        (?!.*(?!\38)\8)    # \38 <= \8
                        .*(?=\16$)\41$     # \41 == \16
                    )
                )
                (\25\31\31\35){2}\43$      # 2*(\25 + 2*\31 + \35) + \43
            )
        )
        ^.*
    )
)
\20
|xx?\B|                        # handle inputs in the domain ^x{0,4}$

```

---

# Regex (ECMAScript)

I have not yet ported this algorithm to basic ECMAScript. One way to do it would be to use \\$k=\lceil\sqrt\[\uproot{1}3\]N\rceil\\$ as the number base, and calculate:

$$N^2=(A k^2+B k+C)^2=A^2 k^4 + 2 A B k^3 + (2 A C + B^2)k^2 + 2 B C k + C^2$$

Another way would be to stick with \\$k=\lceil\sqrt N\rceil\\$, capture \\$M\\$ encoded into two or more backrefs, and emulate the existing calculations within the smaller available space. I'm not sure which way would be more concise. Either way, I expect the regex would roughly double in length.
> 79 votes

# Answer
# Python 3, ~~19~~ 17 bytes

A different python answer

```
lambda x:x//2**.5

```

*-2 bytes* thanks to @Mukundan

try it online
> 15 votes

# Answer
# Scratch 3.0, ~~7~~ 5 blocks/~~62~~ 36 bytes

Try it on~~line~~ Scratch!

As SB Syntax:

```
define(n
say(round((n)/([sqrt v]of(2

```

It's always fun to usual visual languages! At least I have built-ins this time.

*-26 bytes thanks to @att*
> 15 votes

# Answer
## JavaScript (ES6), 12 bytes

```
i=>i/2**.5|0

```

Uses a binary or to truncate the result

Try it online!
> 12 votes

# Answer
# 8087 FPU machine code, 11 bytes

Unassembled listing:

```
D9 E8   FLD1                    ; load a 1 constant (need to make a 2)
D8 C0   FADD ST, ST(0)          ; ST = 1+1 = 2
D9 FA   FSQRT                   ; ST = SQRT(2)
DE F9   FDIVP ST(1), ST         ; ST = N / ST
DF 1F   FISTP QWORD PTR [BX]    ; *BX = ROUND(ST)
C3      RET                     ; return to caller

```

Input in `ST0`, as a 80-bit extended precision value, output to `QWORD PTR [BX]`.

Floating point operations done in x87 math coprocessor hardware with 80-bit extended precision. Correctly calculates values of `N` up to `13043817825332782211`, after which the result will exceed \\$2^{63}-1\\$ (overflowing a 64-bit signed integer return variable).

Example test program with I/O:

(Test program now with 64 bit I/O routines thx to suggestions from @PeterCordes)

Thanks to @PeterCordes for the suggestion take input in `ST(0)`, saving 2 bytes.
> 12 votes

# Answer
# Java 8, 18 bytes

```
n->n/=Math.sqrt(2)

```

Limited to a maximum of \\$9{,}223{,}372{,}036{,}854{,}775{,}807\\$ (signed 64-bit integer).

Try it online.

**Explanation:**

```
n->                // Method with long as both parameter and return-type
  n/=              //  Divide the input by:
     Math.sqrt(2)  //   The square-root of 2

// The `/=` sets the divided result back to `n`, which implicitly casts the resulting double
// back to long. This saves bytes in comparison to `n->(long)(n/Math.sqrt(2))`

```

# Java 9, ~~76~~ 74 bytes

```
n->n.divide(n.valueOf(2).sqrt(new java.math.MathContext(n.precision())),4)

```

-2 bytes thanks to *@OlivierGrégoire*.

Arbitrary I/O and precision.

Try it online.

**Explanation:**

```
n->               // Method with BigDecimal as both parameter and return-type
  n.divide(       //  Divide the input by:
    n.valueOf(2)  //   Push a BigDecimal with value 2
     .sqrt(       //   Take the square-root of that
           new java.math.MathContext(n.precision())),
                  //   with the same precision as the input
    4)            //  With rounding mode HALF_UP

```
> 10 votes

# Answer
# Jelly, 15 bytes

```
³²:2_²:Ẹ¡:2+µƬṪ

```

Try it online!

An arbitrary precision Jelly answer that uses the Newton-Raphson method to find the correct answer. Uses only integer arithmetic operations so the intermediate values are all Python big ints rather than getting cast as floats which would lose precision. The integer result equates to the floor of what would be the floating point answer.

A full program that takes a (possibly negative) integer as its argument and returns an integer.

Now correctly handles inputs of 0 and 1; previously threw an error because of division of 0 by 0 being impermissible for integers.

Useful comment from @PeterCordes about efficiency of this method and some detail on Python’s big integer implementation:

> Newton-Raphson converges quickly, like twice as many correct bits per iteration, given a decent first estimate. e.g. one step refines a 12-bit-precision rsqrtps(x) FP result into nearly 24-bit. (In this case apparently the original input is close enough). You only pay Python interpreter overhead per operation, not per limb (aka chunk) of a very long number; extended-precision division is not cheap but it is implemented in C on chunks of 2^30 stored in an array of 32-bit integers. (I forget if Python uses 64-bit on 64-bit machines.)

## Explanation

```
            µƬ   | Do the following as a monad until no new values seen, collecting up the intermediate values:
³                | - Original argument to program
 ²               | - Squared
  :2             | - Integer divide by 2
    _²           | - Subtract current estimate squared
      Ẹ¡         | - If non-zero:
        :        |   - Integer divide by current estimate
         :2      | - Integer divide by 2
           +     | - Add to current estimate
              Ṫ  | Finally, take the tail of the list of estimates

```

Note `Ẹ¡` is literally repeat the number of times indicated by applying the any function to current value, but it is effectively used here to mean if non-zero.

A much shorter answer that is only accurate to float precision is:

# Jelly, 4 bytes

```
2½:@

```

Try it online!
> 9 votes

# Answer
# Regex (.NET), ~~106~~ 90 bytes

`(?=(x*)(\1x?))(x*).*$(?<=(?=(?<-5>x)*\1(?<=\3))^\2((?<=(?=\6?(\3)*(?<=(?=\3$)(x*))).*)x)*)`

Try it online!

Takes its input in unary, as a sequence of `x` characters whose length represents the number. Returns its output in group `\3`.

By the very nature of this solution, its best-golfed form rounds arbitrarily – sometimes up, sometimes down. As such, it's more complicated to explain why it works, so I suggest reading the explanation of the **104 byte** always-round-down solution below first. (This is oddly appropriate, given the order of operations in regexes that use right-to-left evaluated variable-length lookbehind.)

Compared to the always-round-down solution, this regex takes a shortcut. Instead of counting the number of times the anti-remainder was subtracted, it uses \\$\lfloor{N\over 2}\rfloor\\$ in place of that count. For even values of \\$N\\$ this is \\$1\\$ greater than the actual number of times the anti-remainder was subtracted (since it's never subtracted on the first iteration, and always subtracted on each subsequent iteration). As such, sometimes it doesn't change the resulting returned value \\$M\\$, but sometimes it results in finding an \\$M\\$ that is \\$1\\$ greater than the value it would otherwise have, i.e. \\$\lceil{N\over\sqrt 2}\rceil\\$ instead of \\$\lfloor{N\over\sqrt 2}\rfloor\\$.

For odd values of \\$N\\$, adding \\$1\\$ to that count effectively simulates the extra loop iteration done on \\$\lfloor{N\over 2}\rfloor\\$ in the always-round-down regex. The thing is, without actually doing that, we don't know whether the final value of the anti-remainder was greater than \\$\lfloor{N\over 2}\rfloor\\$ or not. Iff it was greater, then the anti-remainder subtraction count wouldn't have been incremented by \\$1\\$. Thus, by unconditionally effectively adding that \\$1\\$, we're doing the same thing for odd \\$N\\$ as we are for even \\$N\\$ – giving a return value of \\$M\\$ that is arbitrarily rounded up or down.

```
                # tail = N = input number
(?=
    (x*)        # \1 = floor(N / 2)
    (\1x?)      # \2 =  ceil(N / 2)
)
(x*)            # \3 = guessed value of round(sqrt(N*N/2)) - may be rounded up or down
.*$             # tail = 0; head = N
(?<=
                          # head = 0
    (?=
        (?<-5>x)*         # head += \5.capture_count
        \1                # head += \1; this is 1 more than the actual number of times
                          # \6 was subtracted, which will change the \3 result for some
                          # even values of N from rounded-down to rounded-up. But for
                          # odd values of N, it simulates subtracting \6 from the last
                          # half-chunk, which is not covered in the loop we did. Note
                          # that depending on the final value of \6, it may be <= \1,
                          # in which case we'll get a rounded-down \3, or > \1, in which
                          # case we'll get a rounded-up \3.
        (?<=\3)           # assert head ≥ \3
    )
    ^\2                   # force the loop below to iterate \1 times; head = 0
    (
        (?<=
                          # tail = N
            (?=
                \6?       # tail -= \6, if \6 is set
                (\3)*     # X = floor(tail / \3); tail -= \3*X; \5.capture_count += X;
                          # note that in practice, 0 ≤ X ≤ 1;
                          # Y = tail = remainder
                (?<=
                    (?=\3$)   # assert tail == \3
                    (x*)      # \6 = \3 - Y
                )
            )
            .*            # tail = N
        )
        x                 # head -= 1; tail += 1
    )*
)

```

# Regex (.NET), ~~166~~ ~~104~~ 99 bytes

`(?=(x*)(\1x?))(x*).*$(?<=(?=(?<-5>x)*(?<=\3))^\1(x(?<=(?=(\6)?(?<5>\3)*(?<=(?=\3$)(x*)))(.+\2)?))*)`

Try it online!

Takes its input in unary, as a sequence of `x` characters whose length represents the number. Returns its output in group `\3`.

This solution always rounds down, returning \\$M=\lfloor{N\over\sqrt 2}\rfloor\\$. It accomplishes this by calculating \\$M=\lfloor\sqrt{N^2\over 2}\rfloor\\$, which is done by searching for the largest value of \\$M\\$ for which \\$\lfloor{{N^2\over 2}/M}\rfloor\ge M\\$. A regex can't directly operate on values larger than the input, so this must be done by looping multiple times over \\$N\\$ instead of directly operating on \\$N^2\\$.

For even values of \\$N\\$ this is straightforward enough; we just loop over \\$N/2\\$ copies of \\$N\\$, subtracting \\$M\\$ from it as many times as will fit (which will be \\$0\\$ or \\$1\\$), taking note of the remainder, and then subtracting the corresponding "anti-remainder" (the remainder's difference from \\$M\\$) at the beginning of the next loop iteration. Then the value of \\$\lfloor{{N^2\over 2}/M}\rfloor\\$ is the sum of the number of times \\$M\\$ was subtracted and the number of times the anti-remainder was subtracted. This works because for even \\$N\\$, we have \\$\lfloor{N^2\over 2}\rfloor = \lfloor{N\over 2}\rfloor N\\$.

For odd values of \\$N\\$, we do the above, but then do \\$1\\$ extra loop iteration, subtracting from \\$\lfloor{N\over 2}\rfloor\\$ instead of \\$N\\$. This works because for odd \\$N\\$, we have \\$\lfloor{N^2\over 2}\rfloor = \lfloor{N\over 2}\rfloor N + \lfloor{N\over 2}\rfloor\\$.

The number of times \\$M\\$ and the anti-remainder were subtracted are counted using the .NET feature of balanced groups, with `(?<-5>x)*` below.

```
                # tail = N = input number
(?=
    (x*)        # \1 = floor(N / 2)
    (\1x?)      # \2 =  ceil(N / 2)
)
(x*)            # \3 = guessed value of floor(sqrt(N*N/2))
.*$             # tail = 0; head = N
(?<=
                          # head = 0
    (?=
        (?<-5>x)*         # head += \5.capture_count
        (?<=\3)           # assert head ≥ \3
    )
    ^\1                   # force the loop below to iterate \2 times; head = 0
    (
        x                 # head -= 1; tail += 1
        (?<=
                          # tail = \1 if N is odd and this is the last iteration, or N otherwise
            (?=
                (\6)?     # if \6 is set: tail -= \6; \5.capture_count += 1
                (?<5>\3)* # X = floor(tail / \3); tail -= \3*X; \5.capture_count += X;
                          # note that in practice, 0 ≤ X ≤ 1;
                          # Y = tail = remainder
                (?<=
                    (?=\3$)   # assert tail == \3
                    (x*)      # \6 = \3 - Y
                )
            )
            (.+\2)?       # unless N is odd and this is the last iteration: head = 0; tail = N;
                          # else: head = \2; tail = \1
        )
    )*
)

```

This algorithm would not work on a regex flavor lacking variable-length lookbehind (and lookinto), because to loop more than once with a count that scales with \\$N\\$, the regex needs to subtract at least \\$1\\$ from \\$tail\\$ on each iteration (a zero-width loop iteration would result in terminating the loop). Without lookbehind/lookinto, it would be impossible to operate directly on \\$N\\$ after the first iteration. And once the current value of \\$tail\\$ went below the currently tested value of \\$M\\$, it would no longer be possible to operate on the value of \\$M\\$ in any way. Thus forward-declared backreferences, while required by this algorithm, aren't enough on their own.

So, a regex flavor with forward-declared backreferences but no variable-length lookbehind (or lookinto) could probably use an algorithm based on this one, but additional tricks would have to be used to emulate operating on larger numbers. I'm pretty sure it would not have to use the full-fledged algorithm of my ECMAScript solution, but I haven't worked out the details yet.

# Regex (PCRE+`(?^=)`<sup>RME</sup>), 81 bytes

```
(?=(x*)(\1x?))(x*)(?^1=(x(?^=\8?(\3(?^=(\6?x)))*(x*)(?^3=\7(x*))))*)(?^3!\6?+\1x)

```

Try it on replit.com!

This is a port of the 90 byte .NET regex that rounds arbitrarily. It uses features available in PCRE, in addition to **lookinto**, a feature just added to RegexMathEngine. The fact that even after converting the use of .NET balancing groups to group-building, this regex is still 9 bytes smaller than the .NET version, demonstrates just how much expressibility is available with lookinto. The regex is also much easier understand in this form. (Lookinto is equal in power to variable-length lookbehind, i.e. there's nothing one can do that the other can't.)

```
            # tail = N = input number
(?=
    (x*)    # \1 = floor(N / 2)
    (\1x?)  # \2 =  ceil(N / 2)
)
(x*)        # \3 = guess for round(sqrt(N*N/2)) - may be rounded up or down
(?^1=       # Lookinto: tail = \1
    (
        x          # tail -= 1
        (?^=       # Atomic lookinto: tail = N
            \8?        # tail -= \8, if \8 is set
            # X = floor(tail / \3); tail -= \3*X; \6 += X;
            # Note that in practice, 0 ≤ X ≤ 1
            (
                \3           # Assert tail ≥ \3; tail -= \3
                (?^=
                    (        # \6 = sum of the following:
                        \6?  # previous value of \6 if set, 0 otherwise
                        x    # 1
                    )
                )
            )*         # Match the above as many times as possible, minimum 0
            (x*)       # \7 = tail = remainder = dividend % \3
            (?^3=      # Atomic lookinto: tail = \3
                \7     # tail -= \7
                (x*)   # \8 = tail = \3 - \7
            )
        )
    )*            # Iterate as many times as possible, which will be exactly \1
)
(?^3!       # Negative lookinto: tail = \3
    # Assert \3 ≤ \6 + \1 (outside the negative lookinto), by asserting here
    # that tail ≥ \6 + \1 + 1.
    \6?+          # Take advantage of the fact that it is guaranteed \6 ≤ \3,
                  # meaning we don't have to use "(?(6)\6)".
    \1x
    # Note that \6 + \1 is 1 more than the actual number of times \8 was
    # subtracted, which will change the \3 result for some even values of N
    # from rounded-down to rounded-up. But for odd values of N, it simulates
    # subtracting \8 from the last half-chunk, which is not covered in the loop
    # we did. Note that depending on the final value of \8, it may be ≤ \1, in
    # which case we'll get a rounded-down \3, or > \1, in which case we'll get
    # a rounded-up \3.
)

```

# Regex (PCRE+`(?^=)`<sup>RME</sup>), ~~123~~ ~~113~~ ~~96~~ 95 bytes

`(?=(x*)(\1x?))(x*)(?^=((?=(\2$|))x(?^=((?^=(\7?x))(^\10|\3))*\5(x*)(?^3=\9(x*))))*\1(?^7=\3)|$)`

Try it on replit.com!

This is a port of the 99 byte .NET regex that rounds down.

```
               # tail = N = input number
(?=
    (x*)       # \1 = floor(N / 2)
    (\1x?)     # \2 =  ceil(N / 2)
)
(x*)           # \3 = guess for floor(sqrt(N*N/2))
(?^=           # Atomic lookinto: tail = N
    (
        (?=(\2$|)) # \5 = \2 if tail == \2, 0 otherwise;
                   # Note that if tail==\2, it means this is the last iteration
                   # if N is odd – but if N is even, this iteration will fail to
                   # match, as the last iteration will have already finished.
        x          # tail -= 1
        (?^=       # Atomic lookinto: tail = N
            # if \10 is set: tail -= \10; \7 += 1;
            # X = floor((tail - \5) / \3); tail -= \3*X; \7 += X;
            # Note that in practice, 0 ≤ X ≤ 1
            (
                (?^=
                    (        # \7 = sum of the following:
                        \7?  # previous value of \7 if set, 0 otherwise
                        x    # 1
                    )
                )
                (
                    ^\10   # On the first iteration, if \10 is set, tail -= \10
                |
                    \3     # Assert tail ≥ \3; tail -= \3
                )
            )*         # Match the above as many times as possible, minimum 0
            \5         # tail -= \5
            (x*)       # \9 = tail = remainder = dividend % \3
            (?^3=      # Atomic lookinto: tail = \3
                \9     # tail -= \9
                (x*)   # \10 = tail = \3 - \9
            )
        )
    )*
    \1          # Assert tail ≥ \1, forcing the loop above to iterate \2 times
    (?^7=       # Lookinto: tail = \7
        \3      # Assert \3 ≤ tail, i.e. \3 ≤ \7
    )
|
    $       # or N == 0, in which case the output = the input; this needs to be
            # a special case because "(?^7=...)" cannot match if \7 is unset.
)

```
> 9 votes

# Answer
# 05AB1E, 3 bytes

```
2t÷

```

Try it online!

-1 byte thanks to @Grimmy

Yet another port of my Keg answer for the sake of completion.

## Explained

```
2t÷
2t  # Push the square root of two
  ÷ # Integer division

```

Still no ketchup.
> 7 votes

# Answer
# dc, 5 bytes

```
d*2/v

```

Try it online!

Takes input and leaves output on the stack.

dc automatically uses arbitrary-precision integers, and supports a precision of 0 decimal places by default, thus automatically "rounding". So taking the square-root of 2 will yield 1. Instead, this solution squares the input, by `d`uplicating it and `*` multiplying both the items at the top of the stack, `/` dividing it by `2` (reverse-polish) and takes the `v` square root of that.
> 7 votes

# Answer
# Mathematica, ~~17~~ ~~14~~ 13 bytes / ~~12~~ 7 characters

```
⌊#/√2⌋&

```

Try it online

-3 bytes because Mathematica accepts the char √, which I copied from this MathGolf answer.

-1 byte, -5 characters, as per @Mark S. suggestion, by using `⌊⌋`.

For just one more byte (but 5 more characters) I can always round to the nearest integer with

```
Round[#/√2]&

```
> 6 votes

# Answer
# Japt, 3 bytes

```
z2q

```

Try it

`z` is the floor division method and `q` is the nth-root method, defaulting to square root when it's not passed an argument.
> 6 votes

# Answer
# TI-BASIC, 5 bytes

```
int(Ans√(2⁻¹

```

Built-ins are great.
Input is a number in `Ans`.
Output is what is specified in the challenge.

**Explanation:**

```
       √(2⁻¹   ;get the square root of 1/2
    Ans        ;get the input (Ans)
               ;implicit multiplication
int(           ;truncate
               ;implicit print of Ans

```

---

**Note:** TI-BASIC is a tokenized language. Character count does *not* equal byte count.
> 4 votes

# Answer
# C (gcc) -lm, <sup>~~23~~ \\$\cdots\\$ ~~50~~</sup> 27 bytes

Saved 6 bytes thanks to a'\_'!!!
Added 38 bytes to fix type error kindly pointed out by S.S. Anne.
Saved 3 bytes thanks to rtpax!!!
Saved a whopping 23 bytes thanks to an idea from ErikF!!!

```
#define f(n)ceil(n/sqrt(2))

```

Try it online!
> 4 votes

# Answer
# Brainlove, 73 70 74 61 35 bytes

### Because brainfuck is too hard

-3 bytes by myself, rearranging the memory and fixing some bugs

+4 bytes by myself, fixing an error

-13 bytes by myself

-26 bytes by myself, actually using the Brainlove features properly.

```
[$[->+<]!-]+>[<$[>[-~]<-]!++>>+<]>-

```

Try it online

First computes the sum $$ S = \sum\_{i=1}^n i = \frac{n(n+1)}{2} $$ and then the square root by finding the largest n for which $$ \sum\_{i=1}^n 2i-1 = n^2 \< S $$ The error is always $$ E= \sqrt{\frac{n(n+1)}{2}}- \frac{n}{\sqrt{2}} \< \sqrt{\frac{(n+\frac{1}{2})^2}{2}} - \frac{n}{\sqrt{2}} = \frac{n+\frac{1}{2}-n}{\sqrt{2}} = \frac{\sqrt{2}}{4} $$ and it is counteracted by rounding down. It is not very golfed, since I'm not very familiar with golfing in Brainlove/brainfuck, any improvements welcome (or a bf version). It should theoretically work for unbound cells (arbitrary precision), but I didn't have an option to test that. The input and output are on position 0 and 2 on tape, respectively.
> 4 votes

# Answer
# APL (Dyalog Extended), 5 bytes<sup>SBCS</sup>

Full program. Prompts stdin for zero or more numbers.

```
⌈⎕÷√2

```

Try it online!

ceiling of

console input

`÷` divided by

the square root of

`2` two
> 3 votes

# Answer
# Pyth, 6 bytes

The division *auto-casts* the number to a decimal!? (In seriousness, is there a square root function in Pyth?)

```
/Q@2 2

```

Try it online!

# Explanation

```
  @2   2 to the power of
     2 1/2 (effectively calculates math.sqrt(2))
/Q     Divide the (evaluated) input by that number

```
> 3 votes

# Answer
## wx, 3 bytes

It's , with just one instruction added: square root. Turns out that this is very useful! (P.S. the built-in was added before the challenge.)

```
2Q/

```

## Explanation

```
 2Q  % Find the square root of 2
a  / % Divide the input by it
     % If one operand is an integer,
     % the program will automatically
     % try to trunctuate to an integer

```
> 3 votes

# Answer
# PHP, 17 bytes

```
<?=$argn/2**.5|0;

```

Try it online!

Uses @Niphram's truncate method (which in PHP also has the ability to convert the float to an int)

I know it's trendy to say PHP is to be hated, but I kinda came to like its oddities, and it gives me a chance to add an original answer

EDIT: saved 4 bytes using `<?=` php tag (no need to echo)

EDIT2: basically it's just a port of @Niphram's answer now
> 3 votes

# Answer
# Whitespace, ~~122~~ 103 bytes

```
[S S T  T   N
_Push_-1][S S S N
_Push_0][S N
S _Dupe_0][T    N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve_input][S N
S _Dupe_input][N
T   S T N
_If_0_Jump_to_Label_ZERO][N
S S N
_Create_Label_LOOP][S N
T   _Swap_top_two][S S S T  N
_Push_1][T  S S S _Add][S N
T   _Swap_top_two][S N
S _Dupe_input][S N
S _Dupe_input][T    S S N
_Multiply][S T  S S T   S N
_Copy_0-based_2nd_n][S N
S _Dupe_n][T    S S N
_Multiply][S S S T  S N
_Push_2][T  S S N
_Multiply][S N
T   _Swap_top_two][T    S S T   _Subtract][N
T   T   N
_If_neg_Jump_to_Label_LOOP][S N
T   _Swap_top_two][N
S S T   N
_Create_Label_ZERO][T   N
S T _Print_as_integer]

```

Letters `S` (space), `T` (tab), and `N` (new-line) added as highlighting only.
`[..._some_action]` added as explanation only.

Try it online (with raw spaces, tabs and new-lines only).

Output is rounded up.

Inspired by the following mentioned in *@Deadcode*'s Regex answer:

> For input \\$N\\$, we want to calculate \\$M=\left\lfloor\frac{N}{\sqrt2}\right\rfloor\\$. So we want the largest \\$M\\$ such that \\$2M^2\<N^2\\$.

EDIT: My program now implements \\$2M^2\leq N^2\\$ instead to save 19 bytes (\\$\lt\\$ vs \\$\leq\\$ is irrelevant, otherwise \\$\sqrt{2}\\$ would be rational). Although I see *@Deadcode* edited his Regex answer and he's actually using \\$\leq\\$ as well.

**Explanation in pseudo-code:**

```
Integer n = -1
Integer input = STDIN as integer
Start LOOP:
  n = n + 1
  If(n*n*2 - input*input < 0):
    Go to next iteration of LOOP
  Print n
  (exit program with error since no exit is defined)

```

**Example program flow (input `4`):**

```
Command  Explanation                  Stack         Heap     STDIN  STDOUT  STDERR

SSTTN    Push -1                      [-1]
SSSN     Push 0                       [-1,0]
SNS      Duplicate 0                  [-1,0,0]
TNTT     Read STDIN as integer        [-1,0]        [{0:4}]  4
TTT      Retrieve from heap #0        [-1,4]        [{0:4}]
SNS      Duplicate 4                  [-1,4,4]      [{0:4}]
NTSTN    If 0: Jump to Label ZERO     [-1,4,4]      [{0:4}]
         (^ workaround for input=0, since it would otherwise output -1)
NSSSN    Create Label LOOP            [-1,4]        [{0:4}]
SNT       Swap top two                [4,-1]        [{0:4}]
SSSTN     Push 1                      [4,-1,1]      [{0:4}]
TSSS      Add top two: -1+1           [4,0]         [{0:4}]
SNT       Swap top two                [0,4]         [{0:4}]
SNS       Duplicate 4                 [0,4,4]       [{0:4}]
SNS       Duplicate 4                 [0,4,4,4]     [{0:4}]
TSSN      Multiply top two: 4*4       [0,4,16]      [{0:4}]
STSSTSN   Copy 0-based 2nd            [0,4,16,0]    [{0:4}]
SNS       Duplicate 0                 [0,4,16,0,0]  [{0:4}]
TSSN      Multiply top two: 0*0       [0,4,16,0]    [{0:4}]
SSSTSN    Push 2                      [0,4,16,0,2]  [{0:4}]
TSSN      Multiply top two: 0*2       [0,4,16,0]    [{0:4}]
SNT       Swap top two                [0,4,0,16]    [{0:4}]
TSST      Subtract top two: 0-16      [0,4,-16]     [{0:4}]
NTTN      If neg: Jump to label LOOP  [0,4]         [{0:4}]

SNT       Swap top two                [4,0]         [{0:4}]
SSSTN     Push 1                      [4,0,1]       [{0:4}]
TSSS      Add top two: 0+1            [4,1]         [{0:4}]
SNT       Swap top two                [1,4]         [{0:4}]
SNS       Duplicate 4                 [1,4,4]       [{0:4}]
SNS       Duplicate 4                 [1,4,4,4]     [{0:4}]
TSSN      Multiply top two: 4*4       [1,4,16]      [{0:4}]
STSSTSN   Copy 0-based 2nd            [1,4,16,1]    [{0:4}]
SNS       Duplicate 1                 [1,4,16,1,1]  [{0:4}]
TSSN      Multiply top two: 1*1       [1,4,16,1]    [{0:4}]
SSSTSN    Push 2                      [1,4,16,1,2]  [{0:4}]
TSSN      Multiply top two: 1*2       [1,4,16,2]    [{0:4}]
SNT       Swap top two                [1,4,2,16]    [{0:4}]
TSST      Subtract top two: 2-16      [1,4,-14]     [{0:4}]
NTTN      If neg: Jump to label LOOP  [1,4]         [{0:4}]

SNT       Swap top two                [4,1]         [{0:4}]
SSSTN     Push 1                      [4,1,1]       [{0:4}]
TSSS      Add top two: 1+1            [4,2]         [{0:4}]
SNT       Swap top two                [2,4]         [{0:4}]
SNS       Duplicate 4                 [2,4,4]       [{0:4}]
SNS       Duplicate 4                 [2,4,4,4]     [{0:4}]
TSSN      Multiply top two: 4*4       [2,4,16]      [{0:4}]
STSSTSN   Copy 0-based 2nd            [2,4,16,2]    [{0:4}]
SNS       Duplicate 2                 [2,4,16,2,2]  [{0:4}]
TSSN      Multiply top two: 2*2       [2,4,16,4]    [{0:4}]
SSSTSN    Push 2                      [2,4,16,4,2]  [{0:4}]
TSSN      Multiply top two: 4*2       [2,4,16,8]    [{0:4}]
SNT       Swap top two                [2,4,8,16]    [{0:4}]
TSST      Subtract top two: 8-16      [2,4,-8]      [{0:4}]
NTTN      If neg: Jump to label LOOP  [2,4]         [{0:4}]

SNT       Swap top two                [4,2]         [{0:4}]
SSSTN     Push 1                      [4,2,1]       [{0:4}]
TSSS      Add top two: 2+1            [4,3]         [{0:4}]
SNT       Swap top two                [3,4]         [{0:4}]
SNS       Duplicate 4                 [3,4,4]       [{0:4}]
SNS       Duplicate 4                 [3,4,4,4]     [{0:4}]
TSSN      Multiply top two: 4*4       [3,4,16]      [{0:4}]
STSSTSN   Copy 0-based 2nd            [3,4,16,3]    [{0:4}]
SNS       Duplicate 3                 [3,4,16,3,3]  [{0:4}]
TSSN      Multiply top two: 3*3       [3,4,16,9]    [{0:4}]
SSSTSN    Push 2                      [3,4,16,9,2]  [{0:4}]
TSSN      Multiply top two: 9*2       [3,4,16,18]   [{0:4}]
SNT       Swap top two                [3,4,18,16]   [{0:4}]
TSST      Subtract top two: 18-16     [3,4,2]       [{0:4}]
NTTN      If neg: Jump to label LOOP  [3,4]         [{0:4}]

SNT       Swap top two                [4,3]         [{0:4}]
NSSTN     Create Label ZERO           [4,3]         [{0:4}]
TNST      Print as integer to STDOUT  [4]           [{0:4}]         3
                                                                            error

```

Program stops with an error because no exit is defined.
> 3 votes

# Answer
# C (gcc), Precision limited by built-in types, ~~42~~ 36 bytes

```
__int128 f(__int128 n){n/=sqrtl(2);}

```

Try it online!

Floor for the most part but the last output is ceiling.

Uses GCC's `__int128` type: shorter in text length than `unsigned long`, can represent every value in `unsigned long`, and determined to not be a builtin type. Stay tuned for 6-8 weeks to get arbitrary precision.

*-6 bytes thanks to Peter Cordes!*
> 3 votes

# Answer
# Canvas, 4 bytes

```
２√ｎ┐

```

Try it here!
> 3 votes

# Answer
# Dart, 33 bytes

```
import'dart:math';f(a)=>a~/sqrt2;

```

Try it online!
> 3 votes

# Answer
# Keg, 6 bytes

```
21½Ë/ℤ

```

Try it online!

This defines the function `f` as:

* Taking a single parameter, then
* Calculating the square root of 2 by raising it to the power of 0.5, then
* Dividing the parameter by root 2, then
* Casting the result to an integer (truncating / flooring the result) and returning it.

The footer is to define the test cases in a nice way.

## Explained in a usual way

```
21½Ë/ℤ
2   # Push 2 to the stack
 1½ # Push 1 and halve it to get 0.5
   Ë    # Push 2 ** 0.5 (x ** 1/2 = sqrt(x))
    /ℤ  # Divide and cast to integer (floor)

```

Sorry, we're all out of ketchup. You'll have to squeeze your own.
> 2 votes

# Answer
# Python 3, ~~22~~ 21 bytes

```
lambda x:int(x/2**.5)

```

Try it online!

*-1 byte thanks to @RGS. Thanks for reminding me that implicit decimals exist*

Just a port of my Keg answer. Nothing special here.
> 2 votes

# Answer
# Haskell, 20 bytes

```
f n=round$n/(sqrt 2)

```

Try it online
> 2 votes

# Answer
# MathGolf, 4 bytes

```
2√/i

```

Try it online.

**Explanation:**

```
2√    # Take the square-root of 2
  /   # Divide the (implicit) input-integer by this
   i  # Cast it to an integer, truncating any decimal values
      # (after which the entire stack joined together is output implicitly as result)

```
> 2 votes

# Answer
# CJam, 9 bytes

CJam has `mQ`, but unfortunately it trunctuates to an integer ... Another port of Lyxal's answer.

```
q~2 .5#/i

```

Try it online!

## Explanation

```
q~        e# Take input & evaluate
  2       e# Take 2 to the power of ...
    .5#   e# ... 0.5 (equal to square root)
       /  e# Divide the input by it
        i e# Convert to integer

```
> 2 votes

# Answer
# PowerShell, 67 bytes

```
param([uint64]$n)($n/[math]::Sqrt(2)).ToString("G17")-replace'\..*'

```

Try it online!

.NET (and thus, by extension, PowerShell) doesn't have a `BigDecimal`, so we're limited to `Double` or `Decimal`. However, the `[math]::Sqrt()` function only works on `Double`, so there we're stuck. So far, so standard. We then specify precision with `G17`, which successfully round-trips to give us 17 digits of precision on our `Double`, so we can pass everything but the last three test cases. We finish that off with a simple truncation `-replace`.
> 2 votes

# Answer
# JavaScript (Node.js) arbitrary-precision, 62 58 bytes

Thanks to Arnauld saving 4 bytes

```
(n,v=n*n/2n,m=x=>x-(y=v/x+x>>1n)>>1n?m(y):y)=>v<2n?v:m(1n)

```

Try it online!

This is `sqrt(n*n/2)` after golfing the iterative Newton method `sqrt()` from https://stackoverflow.com/a/53684036.
> 2 votes

# Answer
# Burlesque, 8 bytes

```
@2r@|/R_

```

Try it online!

```
@2   # Push 2.0
r@   # Sqrt it
|/   # Cast input to number, divide input by 2
R_   # Round to nearest

```
> 2 votes

# Answer
# Haskell, 32 bytes

```
h n=last[x|x<-[0..n],2*x^2<=n^2]

```

This submission works for arbitrary precision integers, but is very slow because it checks every number \\$x\\$ below \\$n\\$ for whether it satisfies the equation \\$ 2x^2\leq n^2\\$, then takes the last one. Thus the runtime is exponential in the bit length of the input number.

Try it online!

# Haskell, 64 bytes

```
g n|n<2=n|s<-g(n`div`4)*2=last$s+1:[s|(s+1)^2>n]
f n=g$n*n`div`2

```

This submission also works for arbitrary precision integer and is much faster (all test cases instantaneous). It is based on the digit-by-digit integer square root listed on Wikipedia.

Try it online!
> 2 votes

# Answer
# Ruby, 20 bytes

```
->n{(n/2**0.5).to_i}

```

Try it online!
> 2 votes

# Answer
# Husk, 3 bytes

```
÷√2

```

Try it online!

# Explanation

```
 √2  Find the square root of 2 (pretty straightforward).
÷  ⁰ Floor division with the input.
     Note that the numerator is the input, NOT the square root of 2.

```
> 2 votes

# Answer
# AppleSoft BASIC, 24 bytes

The (js) emulator allows for huge integers (and is way too fast), but a real Apple II would have overflowed at 1000000. Integer values have a fixed range of -32767 to 32767.

The 24-byte "function":

```
9?INT(N/SQR(2)):RETURN

```

The full test program:

```
0DATA0,1,2,3,4,5,10,32,500,1000,1000000,186444716,1000000000,2147483647,3037000499
1FORI=1TO15:READN:GOSUB9:NEXT:END
9?INT(N/SQR(2)):RETURN

```
> 2 votes

# Answer
# Scratch, 62 bytes

```
when gf clicked
ask()and wait
say(round((answer)/([sqrt v]of(2

```
> 2 votes

# Answer
# MMIX, 36 bytes (9 instrs)

```
3FFF0001 F60100FF 3B00003F
E0FFB5D4 E5FFF333 E6FFF9DE
E7FF6484 1E0000FF F8010000

```

# Explanation

`3FFF0001`: `SRU $255,$0,1`
`F60100FF`: `PUT rD,$255` Put input / 2 in hidiv register.
`3B00003F`: `SLU $0,$0,1` Multiply input by \\$2^{63}\\$ (mod \\$2^{64}\\$).
`E0FFB5D4`: `SETH $255,#B5D4`
`E5FFF333`: `INCMH $255,#F333`
`E6FFF9DE`: `INCML $255,#F9DE`
`E7FF6484`: `INCL $255,#6484` Set temp to \\$\lfloor\sqrt2\mathop\cdot2^{63}\rfloor\\$.
`1E0000FF`: `DIVU $0,$0,$255` Divide \\$2^{63}\\$ times input by temp.¹
`F8010000`: `POP 1,0` Return one register

The value of `0xb5d4f333f9de6484` I used for \\$\sqrt2\mathop\cdot2^{63}\\$ was hand-calculated by bisecting search.

1. `DIVU $X,$Y,$Z` sets `$X` to the quotient of `rD * 2^64 + $Y` divided by `$Z`, rounding down (and `rR` to the remainder, though it isn't used).
> 2 votes

# Answer
# Perl 5 `-p`, ~~15~~ 13 bytes

```
$_=0|$_/2**.5

```

Try it online!
> 2 votes

# Answer
# Lua, 16 bytes

```
print(...//2^.5)

```

Try it online!
> 2 votes

# Answer
# cQuents, 11 bytes

```
#|1:A_/2^.5

```

Try it online!

## Explanation

```
#|1          output the first term
   :         mode: sequence
             each term equals:
    A        input
     _/            //
       2              2
        ^               **
         .5                .5

```
> 1 votes

# Answer
# Charcoal, 46 bytes

```
≔⁰θ≔⁰ηＦ↨÷ＸＮ²¦²¦⁴«≔⁺×θ⁴ιθ≦⊗η¿›θ⊗η«≧⁻⊕⊗ηθ≦⊕η»»Ｉη

```

Try it online! Link is to verbose version of code. Performs an arbitrary-precision floored integer square root of `n²/2` using the binary square root algorithm as demonstrated e.g. by Dr. Math. Explanation:

```
≔⁰θ≔⁰η

```

Set the accumulator and result to zero.

```
Ｆ↨÷ＸＮ²¦²¦⁴«

```

Loop over the base 4 digits of `n²/2`.

```
≔⁺×θ⁴ιθ

```

Multiply the accumulator by 4 and add the next digit.

```
≦⊗η

```

Double the result.

```
¿›θ⊗η«

```

If the accumulator is greater than double the doubled result, ...

```
≧⁻⊕⊗ηθ≦⊕η

```

... then subtract the incremented doubled result from the accumulator and increment the result.

```
»»Ｉη

```

Print the result once all of the digits have been processed.
> 1 votes

# Answer
# , 19 bytes

```
function(i)i%/%2^.5

```

Try it online!
> 1 votes

# Answer
# Pari/GP, 17 bytes

Another arbitrary-precision answer.

```
n->sqrtint(n^2\2)

```

Try it online!
> 1 votes

# Answer
# AWK, ~~19~~ 17 bytes

```
1,$0=int($0/2^.5)

```

Try it online!
> 1 votes

# Answer
# Zsh, 17 bytes

Built-ins only. No need to use `zmodload zsh/mathfunc` as basic math capabilities of `zsh` are pretty decent. Correct up to `4503599627370496`, after that it overflows. Try it Online!

```
<<<$[(n/2**.5)^0]

```
> 1 votes

# Answer
# Vyxal, 3 bytes

```
2√ḭ

```

Try it Online!
> 1 votes

# Answer
# Raku, 11 bytes

```
0+|*/2.sqrt

```

Try it online!
> 1 votes

# Answer
# Desmos, 20 bytes

```
f(n)=floor(n/\sqrt2)

```

Try it on Desmos!
> 1 votes

# Answer
# Thunno, \\$ 3 \log\_{256}(96) \approx \\$ 2.47 bytes

```
2t,

```

Attempt This Online!

`2` pushes 2; `t` square roots it; `,` does integer division.
> 1 votes

# Answer
# , 9 bytes

```
<.@%2%:2:

```

Attempt This Online!

```
<.@%2%:2:
       2:  NB. literal 2
    2%:    NB. sqrt
   %       NB. division
  @        NB. then
<.         NB. floor

```
> 1 votes

# Answer
# Trilangle, 41 bytes

```
<2?:2'L0'*<....'~~*22.L(-Sj2,7>~,!@..._.^

```

Outputs the larger number for even inputs, and the smaller number for odd inputs. Doesn't work for numbers larger than 4096 due to the integer limit, and for 4096 exactly it invokes UB but still outputs a valid result on my machine.

Try it in the online interpreter!

For the lack of floating-point numbers or a sqrt builtin, this computes the smallest nonnegative integer \\$m\\$ for which \\$m^2 \ge n\left\lfloor\frac{n}{2}\right\rfloor\\$. It turns out to be slightly more compact to add some bitwise complement instructions, replacing `++m` with `m = ~m; --m; m = ~m`.
> 1 votes

# Answer
# FRACTRAN, 15 14 fractions

-1 fraction thanks to my stupidity

```
22/35 14/55 1/14 1/22 15/2 14/5 143/119 91/187 3211/11 17/39 143/17 13/3 1/13 1/7

```

Try it online

A port of my Brainlove answer. Accepts input as 2^n, returns as 19^n.
> 1 votes

# Answer
# Thunno 2, 3 bytes

```
2ƭ÷

```

Attempt This Online!

#### Explanation

```
2ƭ÷  # Implicit input
     # n
  ÷  #   //
 ƭ   #      sqrt( )
2    #           2
     # Implicit output

```
> 1 votes

# Answer
# Python 3.8 (pre-release), 40 bytes

All other python answers are limited to integers smaller than about `10**16`.

Here is one that works with all python integers, giving the correct result even for arbitrarily large integers. Always rounds down.

```
lambda x:isqrt(x*x//2)
from math import*

```

Try it online!
> 1 votes

# Answer
# JavaScript (Node.js), 31 bytes

```
n=>(g=i=>i*i*2<n*n?g(++i):i)(0)

```

Try it online!

or BigInt version, anyway really large values impractical to run

Brute-force i till reach
> 1 votes

# Answer
# Clarion, 58 bytes

Takes an integer input as the first command-line parameter, and displays the result in a Win32 MessageBox

```
Program
 Map.
Code
 Stop(Round((Command(1)/Sqrt(2)),1))

```
> 0 votes

# Answer
# Arturo, 17 bytes

```
$=>[floor&/2^0.5]

```

Try it
> 0 votes

# Answer
# Nibbles, 4.5 bytes (9 nibbles)

```
^/*$$~-2

```

```
  *         # multiply
   $        # input
    $       # by itself,
 /          # divide by
     ~      # 2,
^     -2    # and get the square-root

```
> 0 votes

---
Tags: code-golf, math, number, arithmetic
---


title: Minimum excluded number

text:
# Question
Title: 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

```

# Answer
> 10 votes
# 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]

```

# Answer
> 6 votes
## 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

# Answer
> 5 votes
# 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.

# Answer
> 5 votes
# Brachylog, 4 bytes

```
ℕ≜¬∈

```

Try it online!

Works for any list size and any integer magnitudes.

Takes input from the Output variable, and outputs to the Input variable.

### Explanation

```
ℕ      We want a non-negative integer
 ≜     Assign a value such that…
  ¬∈   …it is not an element of the list

```

# Answer
> 5 votes
# Jelly, ~~5~~ 4 bytes

```
0ḟ1#

```

Try it online!

Doesn't use the bounds on the input.

...am I missing something?

```
0       Starting with 0,
  1#    find the first integer
 ḟ      which is not in the input.

```

# Answer
> 4 votes
# 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

# Answer
> 4 votes
# 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
$

```

# Answer
> 4 votes
# 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\\\\<\]

# Answer
> 4 votes
# Jelly, 7 bytes

```
Ṁ‘‘Ḷḟ⁸Ḣ

```

Try it online!

## How it works

```
Ṁ‘‘Ḷḟ⁸Ḣ  Main Link; argument is z
Ṁ‘‘      Takes 2 above the largest element in z
   Ḷ     Takes lowered range (thus returning [0, ..., max(z) + 1])
    ḟ⁸   Exclude all elements from the range that are also in z
      Ḣ  Take the first element (which is the smallest)

```

Thanks to @LeakyNun for -1 byte!

# Answer
> 4 votes
# Trilangle, 53 bytes

```
'0.<_.\.>?0e#L_'\r/(&\,<.|.1.2S<.^#':2',.<..^\,!@.^)S

```

I'm not convinced this is optimal, but I've thought about it for a while and I don't think I can shrink it without substantial restructuring. I have proven that it's impossible to do this general approach without at *least* a grid of size n=8, and this is n=10.

Try it on the online interpreter!

Unfolds to this:

```
         '
        0 .
       < _ .
      \ . > ?
     0 e # L _
    ' \ r / ( &
   \ , < . | . 1
  . 2 S < . ^ # '
 : 2 ' , . < . . ^
\ , ! @ . ^ ) S . .

```

Equivalent to this C code:

```
#include <stdio.h>

// Read an integer from stdin, throwing out any separators. Returns -1 on EOF.
// Exact implementation is unimportant (and provided by the interpreter).
extern int getint(void);

int main() {
    // RED PATH
    // Keep a bitfield of the numbers that have been seen so far
    int field = 0;
    int i;
    while ((i = getint()) >= 0)
        // GREEN PATH
        field |= 1 << i;

    // BLUE PATH
    // Find the lowest nonzero bit
    int missing = 0;
    while (field & 1) {
        // MAGENTA PATH
        field >>= 1;
        ++missing;
    }

    // YELLOW PATH
    printf("%d\n", missing);
}

```

I am not doing an instruction-by-instruction walkthrough of this code. If you're interested, you can look into the disassembly feature of the interpreter.

# Answer
> 4 votes
# Vyxal `gH`, 2 bytes

```
ʀ⊍

```

Try it Online! (Includes test cases)

```
   # H flag presets the stack to 100
ʀ  # inclusive range 0..100
 ⊍ # set difference
   # g flag takes the minimum of the top of stack after execution
   # which is implicitly output

```

# Answer
> 4 votes
# Nekomata, 2 bytes

```
ᵏf

```

Attempt This Online!

```
ᵏf
ᵏ   Find the first natural number n such that:
 f  the input does not contain n

```

# Answer
> 3 votes
## Ruby, 32 bytes

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

```

Defines a function `f` to be called with an array.

# Answer
> 3 votes
# 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!

# Answer
> 3 votes
# Perl 6, ~~18~~ 16 bytes

*-2 bytes thanks to nwellnhof*

```
{(0...*∉@_)-1}

```

Try it online!

Anonymous code block that counts up until it finds a number that is not an element of the input list, and returns the length of the range minus one

# Answer
> 3 votes
# 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

```

# Answer
> 3 votes
# Rust, ~~117, 113, 79~~ 78 bytes

```
|l:&[u8]|{let mut r:Vec<_>=(0..22).collect();r.retain(|n|!l.contains(n));r[0]}

```

Attempt This Online!

## Explanation

```
|l: &[u8]| {
    // Make a vector of the integers from 0 to 21
    let mut r: Vec<_> = (0..22).collect();
    // Keep only the numbers that aren't in the input
    r.retain(|n|!l.contains(n));
    // Return the first remaining number in the vector
    r[0]
}

```

# Answer
> 3 votes
# JavaScript (ES6), 33 bytes

Thanks to @fhuvi for letting me know that my answer to this more recent challenge also works here.

```
a=>a.reduce(m=>m+a.includes(m),0)

```

Try it online!

# Answer
> 2 votes
## GolfScript (10 9 bytes)

```
~.,),^$0=

```

Takes input from stdin in the format `[5 4 1 5 4 8 2 1 5 4 0 7 7]`.

Online demo

# Answer
> 2 votes
# Ruby, 22

```
x=->n{([*0..20]-n)[0]}

```

## Explanation

* Input is taken as an argument to a lambda. It expects an `Array` of `Integer`s.
* 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.

# Answer
> 2 votes
# Xojo, 55 bytes

```
dim x as int8
while a.indexOf(x)>-1
x=x+1
wend
return x

```

# Answer
> 2 votes
# Haskell, 30

```
f s=filter(`notElem`s)[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

```

# Answer
> 2 votes
## 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)
     ))
  )
)

```

# Answer
> 2 votes
# R, 27 bytes

Reads from stdin; computes the first element in the set difference between `[0..20]` and `x`.

```
x=scan()
setdiff(0:20,x)[1]

```

# R, 36 bytes

`which.min(y%in%x)` returns the index of the first element of `y` that is not in `x`.

```
x=scan()
y=0:20
y[which.min(y%in%x)]

```

# Answer
> 2 votes
# Perl 5 `-p`, 28 bytes

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

```

Try it online!

# Answer
> 2 votes
# 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`.

# Answer
> 2 votes
# Prolog (SWI), ~~64~~ 35 bytes

*-29 bytes thanks to @Jo King*

```
L+X:-between(0,20,X),\+member(X,L).

```

Try it online!

# Answer
> 2 votes
# Vyxal `r`, ~~7~~ ~~5~~ 4 bytes

```
₇ʀFg

```

*-2 bytes thanks to lyxal*

*-1 byte thanks to Steffan*

Try it online or verify all test cases.

Explanation:

```
 ʀ    # The range 0 to
₇     # 128
  F   # Filter out items from the range that are in the input list
      # (The r flag swaps the arguments)
    g  # Get the lowest one

```

# Answer
> 2 votes
# Thunno, \\$ 9 \log\_{256}(96) \approx \\$ 7.41 bytes

```
21RAq0sAh

```

Attempt This Online!

#### Explanation

```
21RAq0sAh  # Implicit input                     INPUT: [4, 1, 0, 2]
21R        # Push range(21)                     STACK: [4, 1, 0, 2], [0..20]
   Aq      # Check whether each of the items    STACK: [1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
           # in the input occurs in range(21)
     0sAh  # Find the index of the first 0      STACK: 3
           # (0-indexed)
           # Implicit output

```

# Answer
> 2 votes
# Julia 0.6, 22 bytes

```
>(x,i=0)=i∈x?x>i+1:i

```

Try it online!

Minimally adapted from MarcMush's recursive solution to a related challenge.

Julia 0.6 supports ternary operators without spaces, which were deprecated in 0.7 and removed in 1.0.

# Answer
> 1 votes
# Python, 37 characters

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

```

# Answer
> 1 votes
**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 :)

# Answer
> 1 votes
# 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

```

# Answer
> 1 votes
# PHP, 38 Bytes

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

```

## PHP, 39 Bytes

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

```

# Answer
> 1 votes
# 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

```

# Answer
> 1 votes
# 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!

# Answer
> 1 votes
# APL (Dyalog), 19 bytes

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

```

Try it online!

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

# Answer
> 1 votes
# 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`.

# Answer
> 1 votes
# 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!

# Answer
> 1 votes
# 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

```

# Answer
> 1 votes
## F#, 38 bytes

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

```

Try it online!

Fairly straight-forward to be honest...

# Answer
> 1 votes
# 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!

# Answer
> 1 votes
# APL (Dyalog Classic), 11 bytes

```
f←⊃⊢~⍨0,⍳∘⍴

```

Try it online!

# Answer
> 1 votes
# Wolfram Language (Mathematica), 29 bytes

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

```

Try it online!

# Answer
> 1 votes
# 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.

# Answer
> 1 votes
# Python 2, 36 bytes

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

```

Try it online!

# Answer
> 1 votes
# , 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}

```

# Answer
> 1 votes
# 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

```

# Answer
> 1 votes
# 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

# Answer
> 1 votes
# Zsh, 31 bytes

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

```

Attempt This Online! Outputs via exit code.

# Answer
> 1 votes
# 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)

```

# Answer
> 1 votes
# 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

```

# Answer
> 1 votes
# 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

```

# Answer
> 1 votes
# 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

```

# Answer
> 1 votes
# Haskell, 26 bytes

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

```

Try it online!

# Answer
> 1 votes
# 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.

# Answer
> 1 votes
# x86\_32 machine code, <sup>~~14~~</sup> 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

```

# Answer
> 1 votes
## 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.

# Answer
> 1 votes
# 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

```

# Answer
> 1 votes
# \*\>\<\>, 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!

# Answer
> 0 votes
## 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}'

```

# Answer
> 0 votes
## 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;
}

```

# Answer
> 0 votes
# Cobra - 50

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

```

# Answer
> 0 votes
## 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.

# Answer
> 0 votes
# 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

```

# Answer
> 0 votes
# Pyth, 6 bytes

```
f!}TQZ

```

Test suite

Makes no assumptions on the contents of the list.

##### Explanation:

```
f!}TQZ | Full code
-------+--------------------------------
f    Z | First T starting at 0 such that
 !}TQ  |  T is not in the input

```

# Answer
> 0 votes
# Arturo, ~~27~~ 17 bytes

```
$=>[min--@0..20&]

```

Try it

```
$=>[       ; a function
    min    ; minimum of
    --     ; difference of
    @0..20 ; 0..20, reified
    &      ; and input
]          ; end function

```

# Answer
> 0 votes
# Pyt, 7 bytes

```
05²Ř←\↓

```

Try it online!

```
  05²Ř           generate [0,1,2,...,25]
  ←              get input
  \              set difference
  ↓              get minimum; implicit print

```

# Answer
> 0 votes
# Java 8 (OpenJDK 8), 49 bytes

Solution using only inline stream :

```
l->l.stream().sorted().reduce(0,(a,b)->a<b?a:b+1)

```

Try it online!

# Answer
> 0 votes
# JavaScript (Node.js), 37 bytes

Only 4 bytes above the best JS solution :'(

```
l=>l.sort().map(b=>a=a<b?a:b+1,a=0)|a

```

Try it online!

# Answer
> 0 votes
# Stax, 6 bytes

```
21r|^h

```

Run and debug it

This is my first answer in Stax, so I may be missing some builtin that helps.

# Explanation

```
21r|^h #
21r    # range 0..20
   |^  # setwise difference with the input
     h # first element

```

# Answer
> 0 votes
# GNU sed, 127 bytes

```
s/.*/ & %-,-0123456789#/;:1;s/%0*(.*)(.)(,.*\2)(.)/%0\1\4\3\4/;s/(.)#(.*\1)(.)/\30\2\3/;/ (\S*) .*%0*\1,/b1;s/.*%0*(..*),.*/\1/

```

Try it online!

Without the array limit, six more bytes are needed for the inner loop that handles the `99`-\>`100` case:

```
s/.*/ & %-,-0123456789#/
:1
s/%0*(.*)(.)(,.*\2)(.)/%0\1\4\3\4/
:2
s/(.)#(.*\1)(.)/\30\2\3/
t2
/ (\S*) .*%0*\1,/b1
s/.*%0*(..*),.*/\1/

```

# Answer
> 0 votes
# Z80 machine language, 11 bytes

Base address of list in HL, length in BC.

```
AF C5 E5 ED B1 E1 C1 C0 3C 18 F6

```

Returns with mex in A unless it's at least 256, then never returns. If you replace the last two bytes with `B7 20 F5 C8` then it returns with mex in A if it's at most 255 and with the zero flag OFF, else with 0 in A and zero flag ON.

```
    xor a
l:  push bc
    push hl
    cpir // 8086: repnz scas
    pop hl
    pop bc
    ret nz
    inc a
    jr l

```

The alternative above replaces `jr l` with:

```
    or a
    jr nz,l
    ret

```

---
Tags: code-golf, math
---


title: Parse nested absolute values 2

text:
# Question
Title: Parse nested absolute values 2
**Looking at Arnauld's answer, it seems like this version is not really more difficult than the other version, so I made it an optional requirement of the other challenge**

*The absolute value of a number \\$x\\$ is normally written as \\$|x|\\$. The left and right side of the absolute value uses the same symbol, so it is not immediately obvious how to parse nested absolute values e.g. \\$||1-2|+|3-|4-5|||\\$*

Your goal is to parse such an expression containing nested absolute values:

The expression will be given as a string of characters. For simplicity the expression will only contain single digit numbers (or letters if that is easier in your language), the operators `+` and `-` (you can use any two distinct characters to represent these operations) and the symbol `|` for the left and right side of a absolute value. To make the challenger not too easy, it is allowed for numbers to be directly adjacent to absolute values so (`2|3|` and `|2|3` both are valid expressions). See the first version if you do not want to handle that case

Your output should be the same expression in a form that allows to determine how the absolute values are bracketed.

The output has to satisfy the following rules:

* The expression within a absolute value must not end with an operator ( `+` or `-` )
* The expression within a absolute value cannot be empty
* Each `|` has to be part of exactly one absolute value

You may assume there is a valid way to parse the given input. If there is more than one way to parse the expression you can choose any valid solution.

Examples (all possible outputs):

```
|2|                ->  (2)
|2|+|3|            ->  (2)+(3)
|2|3|-4|           ->  (2)3(-4)
|2|3|-4|           ->  (2(3)-4)
|2|3-|4|           ->  (2)3-(4)
||2||              ->  ((2))
||2|-|3||          ->  ((2)-(3))
|-|-2+3||          ->  (-(-2+3))
|-|-2+3|+|4|-5|    ->  (-(-2+3)+(4)-5)
|-|-2+|-3|+4|-5|   ->  (-(-2+(-3)+4)-5)
||1-2|+|3-|4-5|||  ->  ((1-2)+(3-(4-5)))

```

This is the shortest solution wins.

# Answer
# JavaScript (ES6), 52 bytes

I believe my answer to the other version also works for this one... ¯\\\_(ツ)\_/¯

```
f=s=>s>(s=s.replace(/\|(.*?[\d)])\|/,"($1)"))?f(s):s

```

Try it online!
> 1 votes

---
Tags: code-golf, parsing
---