Hashing 1 : Inverse Factorial - Kattis inversefactorial

$$f(n)=n!$$

Given a value $x$ , find $f^{-1}{(x)}$ [that is, such $n$ so that $f(n)=x$].

Constraints

Solution:⌗

At first, this problem seems too hard.

Suppose, we have a bijective function $H(p)$ which return some small integer value for corresponding $p$.

Hence, we can uniquely represent every $p$ by $H(p)$.

How to make $H(p)$

Now, calculate $y = H(x) = x \text{ (mod m)}$.

Again, calculate $H(n!) = n! \text{ (mod m)}$ , for all $n \in [0,10^{6}]$. And check, if it matches with $y$.

Hence we can find $f^{-1}{(x)}$.

If we choose good $m$ , our probability of collision[that is $H(p)=H(q)$ while $p\neq q$] will be too much low.

If you don’t know how to mod, read this article.

cpp Inverse Factorial