C++ 0ms solution, combination math.


  • 3
    H

    Say m >= n
    (m-1 + n-1)! / ((m-1)!* (n-1)!)

    = (m-1+1 ) * ... * (m-1+ n-1) / 1 * ... * n-1

    class Solution {

    public:

    int uniquePaths(int m, int n) {        // (m-1 + n-1)! / ((m-1)! * (n-1)!) 
        int large = max(m,n) -1;
        int small = min(m,n) -1;
        if (large == 0 || small == 0) return 1;
        long int numerator = 1, denominator = 1;
        for (int i=1; i<=small; ++i){
            numerator *= large + i;
            denominator *= i;
        }
        return numerator/denominator;
    }
    

    };


Log in to reply
 

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