# Odds that a string of N digits contains two or more of the same

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

• Could you include test cases? Do N-digit numbers include ones with leading zeros?
– xnor
Commented Jun 30, 2021 at 12:38
• For any given random number Do you mean uniformly random? Please specify the distribution Commented Jun 30, 2021 at 12:38
• 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? Commented Jun 30, 2021 at 12:43
• 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) Commented Jun 30, 2021 at 12:48
• this is essentially the birthday problem.
– user100752
Commented Jun 30, 2021 at 12:53

# 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.)

• 29 bytes
– xnor
Commented Jul 4, 2021 at 11:43

# 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

• Good explanation, so I guess that Ḷ÷⁵CPC should work, too (my first ever attempt at Jelly...) Commented Jun 30, 2021 at 18:41
• @DominicvanEssen thanks a lot, I missed that. I didn't get past guessing the order of builtins yet either ;)
– ovs
Commented Jul 1, 2021 at 9:21

# 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

• 8 bytes Commented Jun 30, 2021 at 14:00
• Alternate 8 bytes (port of @EliteDaMyth's answer) Commented Jun 30, 2021 at 14:07

# 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


# Wolfram Language (Mathematica), 19 bytes

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


Try it online!

# 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&^


# 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


# 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
• 38 bytes by looking at alternate forms of the expression of WolframAlpha
– ovs
Commented Jul 4, 2021 at 10:16
• @ovs I knew there was an optimization but I couldn't find it. Thanks Commented Jul 4, 2021 at 10:43

# 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!

# Charcoal, 11 bytes

Ｉ⁻¹ΠＥＮ∕⁻χιχ


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

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


Alternative approach, also 11 bytes:

Ｉ⁻¹Π∕⁻χ…⁰Ｎχ


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

       …⁰Ｎ  Range from 0 to input integer
⁻χ     Vectorised subtract from 10
∕     χ Vectorised divide by 10
Ｉ⁻¹Π        Cast product subtracted from 1 to string