DEV Community

loading...

Discussion on: Daily Challenge #203 - Pascal's Triangle

Collapse
vidit1999 profile image
Vidit Sarkar

C++

// calculate nCr in O(r) time
long long binCoef(int n, int r){
    r = min(r, n-r);
    int ans = 1;
    for(int i=0;i<r;i++){
        ans *= (n-i);
        ans /= i+1;
    }
    return ans;
}

// calculate the sum
// sum will be 2nCn
// O(n) solution
long long easyline(int n){
    return binCoef(2*n, n);
}