Avoid integer overflow when calculating factorials. Based on leetcode #62 Unique Paths

Using math for solving many programming problems is the fastest way.
For example, you can solve leetcode #62 Unique Paths mathematically. A result is number of n — 1 combinations from m — 1 + n — 1:

A trivial answer for leetcode #62

And this approach works fine in Python:

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        return math.factorial(n + m - 2) / ( math.factorial(n - 1) * math.factorial(m - 1) );

But it works in C# only for little numbers:

/*
    Time: O(log n) for calculating factorial
    Space: O(1)
*/
public class Solution
{
    public int UniquePaths(int m, int n)
    {
        var result = F(n + m - 2) / (F(n - 1)  *  F(m - 1));
        return  (int) result;
    }
    private static ulong F(int n)
    {
        ulong result = 1;
        for(var i = 1; i <= n; i++)
        {
            result *= (ulong)i;
        }
        return result;
    }
}

We get a wrong answer already at boards 23x12:

[Test]
[TestCase(3, 7, 28)]
[TestCase(3, 2, 3)]
[TestCase(3, 3, 6)]
[TestCase(5, 7, 210)]
[TestCase(10, 10, 48620)]
[TestCase(23, 12, 193536720)] // ulong overflow, actual is 0
public void SolutionTests(int m, int n, int expected)
{
    var actual = new Solution().UniquePaths(m, n);
    Assert.That(actual, Is.EqualTo(expected));
}

To avoid that we can calculate the result on the fly using the definition of factorial:

/*
    Time: O(N) where N = m + n
    Space: O(1)
*/
public int UniquePaths(int m, int n)
{
    double result = 1;
    for (int i = 2; i <= (m + n - 2); i++) {
        result *= i;
        
        if(i <= n - 1)
            result /= i;
            
        if(i <= m - 1)
            result /= i;
    }
    return (int)Math.Round(result);
}

Or, we can improve calculating when notice that we can discard dividing by n — 1:

All we need is to start a cycle from n and add 1 — N to the value in the denominator:

/*
    Time: O(N)
    Space: O(1)
*/
public int UniquePaths(int m, int n)
{
    ulong result = 1;
    for (int i = n; i <= (m + n - 2); i++)
    {
        result *= (ulong)i;
        result /= (ulong)(i - n + 1);
    }
    return (int)result;
}

(This helps us to cancel from float arithmetic.)

That’s all! Pretty simple trick and working solution!