My Math based java solution - 0 ms


  • 1
    R

    If the grid, for example is (37), all we need to do is make some combination of 2 down moves and 6 right moves. So, all we are doing is, calculating 2C8. So, we need to calculate 8! / (2! * (8-2)!) or, 8! / (2! * 6!). Now, 3 factorials are too much for our runtime; so we could be a little more strategic and cancel out the 8! on top with 6! on the bottom with (87) on top(8!/ 6! = 8*7).

    public class Solution {
    public int uniquePaths(int m, int n) {
        int bigger=0, smaller=0;
        if (m>n) {
            bigger = m;
            smaller = n;
        }
        else{
            bigger = n;
            smaller = m;
        }
        double result = 1;
        for(int i=bigger+smaller-2;i>bigger-1;i--){
            result*=i; 
        }
        result /= factorial(smaller-1);
        return (int)result;
    }
    public double factorial(int p){
        if (p==0)
            return 1;
        double result =1;
        for(int i=1;i<=p;i++){
            result *= (double)i; 
        }
        return result;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.