C++ O(n) solution, WITHOUT DP


#1

int Solution::uniquePaths(int A, int B) {

if(A==1 || B==1)
    return 1;
A--;
B--;
int n=A+B,r=A,sum=1;
for(int i=1;i<=r;i++){        //number of paths = number of combinations of the total block distance i.e A+B (A-- and B-- here considering it starts from 1,1) which lead to end, so its (A+B)CA. C being the combination function. to avoid overflow, instead of finding factorials, we just use the formula for nCr= (n-(r-1)/r*nCr-1 
    sum=(n-(i-1))*sum;
    sum/=i;
}

return sum;

}


#2

can i have your contact please i did not understand your approach . so i would like to know your approach