# 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:

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

`[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 0public 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!

## More from Andrei Kruglov

Software Engineer