5
\$\begingroup\$

I have to fill in 2fa codes all day. They're 6-digit strings. One day I noticed that not once did any of these codes contain 6 unique digits, like 198532 There was always at least one double, like 198539 (here it's 9).

For any given uniformly random string of \$N\$ digits in the set \$\{0,1,2,3,4,5,6,7,8,9\}\$, what is the odds for this happening?

Your input is a single positive integer, \$N\$, with \$N \le 10\$

Your output is a number between 0 and 1, which is the probability that a string with \$N\$ digits has at least one repetition.

The shortest code wins

\$\endgroup\$
6
  • 4
    \$\begingroup\$ Could you include test cases? Do N-digit numbers include ones with leading zeros? \$\endgroup\$
    – xnor
    Jun 30, 2021 at 12:38
  • \$\begingroup\$ For any given random number Do you mean uniformly random? Please specify the distribution \$\endgroup\$
    – Luis Mendo
    Jun 30, 2021 at 12:38
  • 1
    \$\begingroup\$ What is the margin of possible values of the input N? Can it exceed 10? Also, should the output be the probability of no repetitions, or the probability of at least one repetition? \$\endgroup\$
    – Luis Mendo
    Jun 30, 2021 at 12:43
  • \$\begingroup\$ I'm not the asker, but non-uniformly distributed 2FA codes would be extremely strange... (and the question title suggests that the output should be the probability of at least one repetition) \$\endgroup\$ Jun 30, 2021 at 12:48
  • 5
    \$\begingroup\$ this is essentially the birthday problem. \$\endgroup\$
    – user100752
    Jun 30, 2021 at 12:53

10 Answers 10

8
\$\begingroup\$

Haskell, 30 bytes

f n=1-product[1,0.9..1.1-n/10]

Try it online!

If we pick, for example, 4 digits sequentially, then the odds of each one being "fresh" is

  • \$10/10\$ for the first digit
  • \$9/10\$ for the second digit (it must ≠ the first digit)
  • \$8/10\$ for the third digit (it must ≠ the first and second digits)
  • \$7/10\$ for the fourth digit (it must ≠ the first, second and third digits)

so the probability of getting 4 unique digits is \$\frac{10}{10}\cdot\frac{9}{10}\cdot\frac{8}{10}\cdot\frac{7}{10}\$, and the probability of not getting 4 unique digits (i.e. some repetition) is one minus that.

In general the answer is $$1 - \prod_{k=0}^{n-1} \frac{10-k}{10}.$$

(Though not required, this formula is also valid for \$N \geq 11\$, where the answer is \$1\$. In that case, this product contains a factor 0, representing the fact that we can't possibly pick an eleventh digit that is different from all ten digits that exist.)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 29 bytes \$\endgroup\$
    – xnor
    Jul 4, 2021 at 11:43
5
\$\begingroup\$

Jelly, 7 6 bytes

Uses the same formula as Lynn's Haskell answer.

-1 byte thanks to Dominic van Essen!

Ḷ÷⁵CPC

Try it online!

Ḷ         lowered range:                    [0, 1, ..., n-1]
 ÷⁵       divide each value by 10           [0/10, 1/10, ..., (n-1)/10]
   C      complement, subtract each from 1  [10/10, 9/10, ..., (11-n)/10]
    P     take the product of all values    (10/10)*(9/10)* ... *(11-n)/10
     C    complement                        1 - (10/10)*(9/10)* ... *(11-n)/10
\$\endgroup\$
2
  • \$\begingroup\$ Good explanation, so I guess that Ḷ÷⁵CPC should work, too (my first ever attempt at Jelly...) \$\endgroup\$ Jun 30, 2021 at 18:41
  • \$\begingroup\$ @DominicvanEssen thanks a lot, I missed that. I didn't get past guessing the order of builtins yet either ;) \$\endgroup\$
    – ovs
    Jul 1, 2021 at 9:21
4
\$\begingroup\$

Vyxal, 9 bytes

₀~εrΠ?↵/⌐

Try it Online!

Me and the boys on our way to port Lynn's Haskell answer be like.

Explained

₀~εrΠ?↵/⌐
₀~εr       # the range (10 - input, 10]
    Π      # the product of that
       /   # divided by
     ?↵    # 10 ** input
        ⌐  # 1 - that
\$\endgroup\$
2
1
\$\begingroup\$

Japt, 10 bytes

ÇnA /AÃ×n1

Try it

ÇnA /AÃ×n1     :Implicit input of integer U
Ç              :Map the range [0,U]
 n             :  Subtract from
  A            :  10
    /A         :  Divide by 10
      Ã        :End map
       ×       :Reduce by multiplication
        n1     :Subtract from 1
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 19 bytes

1-10!/10^#/(10-#)!&

Try it online!

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

J, 13 bytes

1-!*(!%^~)&10

Try it online!

  • 1 minus 1- the factorial of the input ! times *...
  • (!%^~)&10 the input choose 10 divided by 10 raised to the input.

Or, equivalenly:

1-!*!&10%10&^
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 8 bytes

Tses°/1α

Try it online!

Uses a different formula from the Wikipedia page:

$$ 1-{_{365}P_{n} \over 10^n} $$

Ts        # push 10 and swap implicit input n to the front
  e       # number of permutations
   s°     # 10 ** n
     /    # divide: nPr(10, n) / 10 ** n
      1α  # absolute difference from 1
\$\endgroup\$
1
\$\begingroup\$

Python 3, 39 38 bytes

f=lambda x:x and(x-1-f(x-1)*(x-11))/10

Try it online!

  • Thanks to @ovs for -1
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 38 bytes by looking at alternate forms of the expression of WolframAlpha \$\endgroup\$
    – ovs
    Jul 4, 2021 at 10:16
  • \$\begingroup\$ @ovs I knew there was an optimization but I couldn't find it. Thanks \$\endgroup\$
    – Jakque
    Jul 4, 2021 at 10:43
1
\$\begingroup\$

APL(Dyalog Unicode), 13 12 bytes SBCS

Implements the same formula as Lynn's Haskell answer.

1-(×/1-.1×⍳)

Try it on APLgolf!

And 15 bytes with \$1-{1\over 10^n} {10!\over (10-n)!}\$:

10∘(1-*÷⍨⊣÷⍥!-)

Try it on APLgolf!

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 11 bytes

I⁻¹ΠEN∕⁻χιχ

Try it online! Link is to verbose version of code. Explanation:

     N      Input integer
    E       Map over implicit range
        χ   Predefined variable `10`
       ⁻    Subtract
         ι  Current index
      ∕     Divided by
          χ Predefined variable `10`
   Π        Take the product
 ⁻¹         Subtract from 1
I           Cast to string
            Implicitly print

Alternative approach, also 11 bytes:

I⁻¹Π∕⁻χ…⁰Nχ

Try it online! Link is to verbose version of code. Explanation:

       …⁰N  Range from 0 to input integer
     ⁻χ     Vectorised subtract from 10
    ∕     χ Vectorised divide by 10
I⁻¹Π        Cast product subtracted from 1 to string
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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