Rolling Hash Collision Probability

Problem

Model a polynomial rolling hash as a uniform random value in [0, mod). With n distinct strings, the birthday bound gives the probability of at least one collision as 1 - exp(-n * (n - 1) / (2 * mod)). Return that probability clamped to 1.0, and 0.0 when n < 2 or mod < 1.

Hint

For small x, 1 - exp(-x) is about x, which is why large moduli make collisions rare.

Test cases

case 1

in: [1000,20]

expected: 0.1730408660566377

case 2

in: [1000003,1000]

expected: 0.39316508978983655

case 3

in: [2,3]

expected: 0.7768698398515702

case 4

in: [1000000007,1]

expected: 0

Starter codePython

def collision_probability(mod, n):
    # Your code here
    pass

4 test cases · run your code against them in the editor