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;
}

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!

Software Engineer