Hash Crash Finals

The probability that there are no collision after $n$ insertions is $Q_n = \frac{1000\times 999 \times \dots \times (1000-n+1)}{1000^n}$ . Hence the probability that there exist a collision is $P_n = 1 - Q_n$ . The problem wants us to find $n$ such that $P_n \geq 0.5 \rightarrow Q_n \leq 0.5$ . Iterate through all $n$ to find such answer.

1
2
3
4
5
6

Q = 1.00
for i in range(1000):
    Q = val * (1000-i) / 1000
    if val < 0.5:
        print i+1
        break

Birthday Problem