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