Numbers Too Big While Trying To Solve Leetcode Unique Paths Problem

I am trying to solve the Unique Paths problem from LeetCode. Basically, the problem is you're given an m by n grid, and you have to count the number of paths from the top left to the bottom right while only going down or right.

I am doing the mathematical approach, which is pretty complicated to figure out but the basic formula is this:

(m - 1 + n - 1) choose (min(m - 1, n - 1)), and the formula for n choose r is n! / (r! * (n-r)!).

This approach works well, but eventually the factorial goes past the integer limit, so it becomes negative. The next thing I tried was to change everything to long, but then again the numbers became too big for long, too. How can I simplify the numbers so it stays under the limit? Here is my code:

public int uniquePaths(int m, int n) { // The method being called
    return (int) (m == 1 || n == 1 ? 1 : choose((m - 1) + (n - 1), Math.min(m - 1, n - 1)));
}

private long choose(long n, long r) { // Calculated n choose r
    return fact(n) / (fact(r) * fact(n - r));
}

private long fact(long n) { // Calculates factorial of n
    return n == 1 ? 1 : n * fact(n - 1);
}

I know it's possible to simplify it because the answer is an integer, so the number should easily fall under Long.MAX_VALUE.

Here after updating your code to use BigInteger class of java, it got accepted.

import java.math.BigInteger; 

class Solution {
    public int uniquePaths(int m, int n) { // The method being called
        BigInteger mB = BigInteger.valueOf(m);
        BigInteger nB = BigInteger.valueOf(n);
        BigInteger ans =  
                (mB.equals(BigInteger.ONE) || nB.equals(BigInteger.ONE) ? 
                BigInteger.ONE :
                choose(mB.subtract(BigInteger.ONE).add(nB.subtract(BigInteger.ONE)), 
                  mB.subtract(BigInteger.ONE).min(nB.subtract(BigInteger.ONE))));

        return ans.intValue();
    }

    private BigInteger choose(BigInteger n, BigInteger r) { // Calculated n choose r
        return fact(n).divide((fact(r).multiply(fact(n.subtract(r)))));
    }

    private BigInteger fact(BigInteger n) { // Calculates factorial of n
        return n.equals(BigInteger.ONE) ? 
            BigInteger.ONE : 
            n.multiply(fact(n.subtract(BigInteger.ONE)));
    }
}

Okay, I got it. What I need to do is cancel out the bigger number in the denominator. If r is bigger than n-r, then the formula becomes this:

n * n-1 * n-2 ... * r+1 / (n-r)!

And if n-r is bigger than r, the formula becomes this:

n * n-1 * n-2 ... * (n-r)+1 / r!

This makes the bigger number in the denominator smaller and n! smaller too. Here is my code in the end:

public int uniquePaths(int m, int n) { // Method being called
    return (int) (m == 1 || n == 1 ? 1 : choose((m - 1) + (n - 1), Math.min(m - 1, n - 1)));
}

private long choose(long n, long r) { // Calculates n choose r
    return r > n - r ? fact(n, r) / fact(n - r) : fact(n, n - r) / fact(r);
}

private long fact(long n) { // Calculates n!
    return n == 1 ? 1 : n * fact(n - 1);
}

private long fact(long n, long lower) { // Calculates n! with lower bound of lower; that is n * n-1 * n-2 ... * lower+1.
    return n == lower ? 1 : n * fact(n - 1, lower);
}