Simple O(n) solution C++..{ with explanation }


#1

int Solution::uniquePaths(int A, int B)
{
/*
say MxN : 7x3
required steps : (7-1)right + (3-1)down
=6 right =2 down
arrange them to get your answer.
total steps = 6+2 = 8.
arrangement : 8C2 OR 8C6
…way to calculate NCr is better with smaller r.
we can write 8C2 as : 8!/6!2! == 87/2!.
use this approach for less number of computations.
*/

int m=A-1;
int r=B-1;
int N=m+r;
if(m<r) swap(m,r); // so we get n smaller

long long int mul=1;
for(int i=0;i<r;i++)
{
    mul*=N;
    N--;
}// here... we have expanded N! only by r nums ..like 8*7.

long long fact=1;
for(int i=2;i<=r;i++) fact*=i; // r!

mul/=fact;

return mul;

}


#2

Dude thats genius… I was calculating the factorial but could not think of a way to reduce the size.
Thanks for the explanation.:+1::+1: