Find factorial n modulo m faster than O(n)

May 15, 2022

How can I find (n!) % m faster than O(n)?

1 <= n <= 10^18,
1 <= m <= 10^6

>Solution :

You can easily have O(m) time complexity in the worst case (when m is a prime) and it seems to be good enough since you have m <= 1e6 (while n can be up to 1e18). Note, that when n >= m

 n! = 1 * 2 * ... * m * ... * n
                    ^
         factorial is divisible by m

and that’s why

 n! % m == 0       # whenever n >= m

Another implementation detail is that you don’t have to compute n! % m as 1 * 2 * ... * n % m but you can do it as ((..(1 % m) * 2 % m) ... * n % m) in order not to deal with huge numbers.

C# code example

private static int Compute(long n, long m) {
  if (n >= m)
    return 0;

  long result = 1;

  // result != 0 - we can well get 0 and stop looping when m is not prime 
  for (long d = 2; d <= n && result != 0; ++d) 
    result = (result * d) % m;

  return result;
}