# Computing nCr

Hey folks,
Today we are going to talk about how to compute nCr in the programming competitions.

1. Dynamic programming Approach :
From the high school mathematics we know a recursive method to calculate nCr i.e.
C(n,r) + C(n,r-1) = C(n+1,r)
This can also be written as
C(n,r) = C(n-1,r) + C(n-1,r-1)

It’s a very simple DP, as you can see nothing to be afraid of here.

Time complexity = O(n*r)
Space complexity = O(n*r)

2. Expand nCr

```C(n,k) = n!/((n-k)!k!)
[n(n-1)...(n-k+1)][(n-k)...(1)]
= -------------------------------
[(n-k)...(1)][k(k-1)...(1)]
```

this can also be written as

```C(n,k) = 1,                 if k = 0
= (n/k)*C(n-1, k-1), otherwise
```

PuedoCode

3. Using Euler’s theorem and modular multiplicative inverse

Modular Multiplicative Inverse :
In modular arithmetic, the modular multiplicative inverse of an integer ‘a’ modulo ‘m’ is an integer ‘x’ such that
ax = 1 (mod m)

Euler’s theorem :
According to Euler’s theorem, if ‘a’ is coprime…

View original post 620 more words