C++ O(n) solution, WITHOUT DP


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

if(A==1 || B==1)
    return 1;
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 

return sum;



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